Milking Order Optimization

Farmer John has N cows (numbered from 1 to \(N\)) and he has made \(M\) observations about their social hierarchy. Each observation is given as an ordered sequence of some cows, which indicates that the cows should be milked in that order (i.e. for a sequence \(a_1, a_2, \ldots, a_k\), cow \(a_1\) should be milked before cow \(a_2\), cow \(a_2\) before cow \(a_3\), and so on).

Observations are listed in order of priority. Farmer John aims to satisfy as many of the high‐priority observations as possible. Formally, let \(X\) be the maximum number of initial observations (i.e. observations 1 through \(X\)) for which there exists a milking order that meets all the ordering constraints. If several valid orders exist, Farmer John chooses the lexicographically smallest order (i.e. the order that at the first position where they differ, has a smaller cow number). Note that when there are no constraints, the lexicographically smallest order is simply \(1, 2, \ldots, N\).

Your task is to compute the optimal milking order that satisfies the first \(X\) observations.

Input Constraints:
\(1 \le N \le 10^5\)
\(1 \le M \le 5\times10^4\)

Hint: Use a binary search on \(X\) and a lexicographically-minimal topological sort (using a min-heap) for checking if a given set of constraints is feasible.

inputFormat

The first line contains two integers \(N\) and \(M\), representing the number of cows and the number of observations, respectively.

Then \(M\) blocks follow. Each block begins with an integer \(k\) (the number of cows in that observation) followed by \(k\) integers, representing the ordered sequence of cows in that observation.

For example:

4 3
3 1 3 2
3 4 2 1
2 3 4

outputFormat

Output a single line containing \(N\) integers — the optimal milking order. The order must satisfy the maximum number \(X\) of highest-priority observations and be the lexicographically smallest order among all valid orders.

For the sample input above, the output should be:

1 3 2 4

sample

4 3
3 1 3 2
3 4 2 1
2 3 4

1 3 2 4