Milking Order

Farmer John's $N$ cows ($1 \leq N \leq 10^5$), numbered $1 \ldots N$ as always, have far too much time on their hooves. They have worked out a complex social hierarchy around the order in which Farmer John milks them every morning.

After weeks of study, Farmer John has made $M$ observations about that hierarchy ($1 \leq M \leq 50\,000$). Each observation is an ordered list of some of his cows, and it means those cows must be milked in the order in which they appear in the list. For example, if one observation is the list 2, 5, 1, Farmer John must milk cow 2 sometime before cow 5, and cow 5 sometime before cow 1.

The observations are prioritized, so Farmer John wants to maximize the value of $X$ for which his milking order meets the conditions of the first $X$ observations. If several milking orders satisfy those first $X$ conditions, a longstanding tradition says that cows with lower numbers outrank cows with higher numbers, so Farmer John milks the lowest-numbered cows first. More formally, he uses the lexicographically smallest such ordering. An ordering $x$ is lexicographically smaller than an ordering $y$ if for some $j$, $x_i = y_i$ for all $i < j$ and $x_j < y_j$: the two orderings agree up to a point, at which $x$ is smaller.

Help Farmer John determine the best order in which to milk his cows.

The first line contains $N$ and $M$. Each of the next $M$ lines describes one observation. Line $i+1$ describes observation $i$: it starts with the number of cows $m_i$ listed in the observation, followed by the $m_i$ cow numbers in the observed order. The sum of the $m_i$ is at most $200\,000$.

Output $N$ space-separated integers forming a permutation of $1 \ldots N$, the order in which Farmer John should milk his cows.

In the first example, Farmer John has four cows. The first observation says to milk cow 1 before cow 2 and cow 2 before cow 3. The second says to milk cow 4 before cow 2, and the third says to milk cow 3 before cow 4 and cow 4 before cow 1. The first two observations hold together, but all three at once would require cow 1 before cow 3 and cow 3 before cow 1, which is impossible. That leaves two possible orderings, 1 4 2 3 and 4 1 2 3, and the lexicographically smaller one is 1 4 2 3.