P4376 [USACO18OPEN] Milking Order G

Farmer John has $N$ cows ($1 \leq N \leq 10^5$), numbered $1 \ldots N$, who have recently gotten bored. They have developed a complex social hierarchy related to the order in which Farmer John milks them each morning. After several weeks of study, Farmer John has made $M$ observations ($1 \leq M \leq 50{,}000$) about the social structure of his cows. Each observation is an ordered sequence of certain cows, indicating that these cows should be milked in the order shown by the sequence. For example, if one observation is the sequence $2$, $5$, $1$, then Farmer John should milk cow $2$ sometime before cow $5$, and milk cow $5$ sometime before cow $1$. The observations are prioritized, and his goal is to maximize the value $X$ such that his milking order can satisfy the first $X$ observations. When multiple milking orders satisfy the first $X$ observations, Farmer John follows a long tradition: cows with smaller IDs outrank those with larger IDs, so he will milk the smallest-numbered cow first. More formally, if multiple milking orders satisfy these observations, Farmer John uses the lexicographically smallest one. A milking order $x$ is lexicographically smaller than a milking order $y$ if, for some $j$, $x_i = y_i$ holds for all $i < j$, and $x_j < y_j$ (that is, the two orders are identical up to some position, and at that position $x$ is smaller than $y$). Please help Farmer John determine the best order in which to milk the cows.

The first line contains $N$ and $M$. Each of the next $M$ lines describes one observation. Line $i+1$ describes observation $i$: the first number is the number of cows in the observation, $m_i$, followed by a list of $m_i$ integers giving the order of cows in that observation. The sum of all $m_i$ is at most $200{,}000$.

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

In this example, Farmer John has four cows, and his milking order should satisfy the following rules: cow $1$ before cow $2$, and cow $2$ before cow $3$ (first observation); cow $4$ before cow $2$ (second observation); cow $3$ before cow $4$, and cow $4$ before cow $1$ (third observation). The first two observations can be satisfied together, but Farmer John cannot satisfy all rules simultaneously, since that would require cow $1$ before cow $3$ while also having cow $3$ before cow $1$. This means there are two possible milking orders: $1\ 4\ 2\ 3$ and $4\ 1\ 2\ 3$, and the first is lexicographically smaller. Problem source: Jay Leeds. Translated by ChatGPT 5