Milking Order (Gold)#10388

Milking Order (Gold)

1 second

128 megabytes

Hard

Farmer John's $n$ cows, numbered from $1$ to $n$ as always, happen to have too much time on their hooves. As a result, they have worked out a complex social hierarchy related to the order in which Farmer John milks them every morning.

After weeks of study, Farmer John has made $m$ observations about his cows' social structure. Each observation is an ordered list of some of his cows, meaning that these cows should be milked in the same order in which they appear in the list. For example, if one of Farmer John's observations is the list $2, 5, 1$ , Farmer John should milk cow $2$ at some point before cow $5$ , and cow $5$ at some point before cow $1$ .

Farmer John's observations are prioritized, so his goal is to maximize the value $X$ such that his milking order satisfies the conditions given by the first $X$ observations. If several milking orders satisfy these first $X$ conditions, Farmer John follows a long-standing tradition according to which cows with smaller numbers outrank cows with larger numbers, so he would like to milk the lowest-numbered cows first. More formally, if several milking orders satisfy these conditions, Farmer John would like to use the lexicographically smallest one. An order $x$ is lexicographically smaller than an order $y$ if there exists $j$ such that $x_{i} = y_{i}$ x_i = y_i for all $i < j$ i < j and $x_{j} < y_{j}$ x_j < y_j (in other words, the two orders coincide up to some position, at which $x$ has a smaller element than $y$ ).

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

Input

The first line contains two integers $n$ and $m (1 \leq n \leq 1 0^{5}, 1 \leq m \leq 5 \cdot 1 0^{4})$ m~(1 \le n \le 10^5, 1 \le m \le 5 \cdot 10^4). Each of the next $m$ lines describes one observation: the $(i + 1)$ (i + 1)-th line describes observation $i$ and starts with the number $m_{i}$ m_i of cows in the observation, followed by $m_{i}$ m_i integers — the numbers of these cows in the required order. The sum of all $m_{i}$ m_i does not exceed $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Output

Print $n$ integers — a permutation of the numbers from $1$ to $n$ specifying the order in which Farmer John should milk his cows.

Examples

Here, Farmer John has $4$ cows. He should milk cow $1$ before cow $2$ , and cow $2$ before cow $3$ (the first observation); cow $4$ before cow $2$ (the second observation); and cow $3$ before cow $4$ , and cow $4$ before cow $1$ (the third observation). The first two observations can be satisfied simultaneously, but Farmer John cannot meet all three at once, since this would require cow $1$ to come before cow $3$ and cow $3$ to come before cow $1$ .

Therefore, there are two orders satisfying the first two observations: $1, 4, 2, 3$ 1, 4, 2, 3 and $4, 1, 2, 3$ 4, 1, 2, 3; the first one is lexicographically smaller.

Example 1