Milking Order

题目描述

农夫约翰有 $N$ 头奶牛（$1 \leq N \leq 10^5$），照例编号为 $1 \ldots N$，它们似乎有太多空闲时间。因此，它们制定出了一套复杂的社会等级制度，与农夫约翰每天早上给它们挤奶的顺序有关。

经过数周研究，农夫约翰对奶牛的社会结构做出了 $M$ 条观察（$1 \leq M \leq 50,000$）。每条观察都是一个由部分奶牛组成的有序列表，表示这些奶牛应该按照该列表中出现的顺序挤奶。例如，如果某条观察的列表为 2, 5, 1，那么农夫约翰应当在挤奶 5 号牛之前的某个时刻挤奶 2 号牛，并且在挤奶 1 号牛之前的某个时刻挤奶 5 号牛。

农夫约翰的观察是有优先级的，因此他的目标是最大化一个值 $X$，使得他的挤奶顺序满足前 $X$ 条观察所给出的条件。如果存在多个挤奶顺序能满足这前 $X$ 条条件，农夫约翰认为“编号更小的奶牛地位高于编号更大的奶牛”是一项悠久传统，因此他希望尽可能先挤编号小的奶牛。更正式地说：若有多个挤奶顺序满足这些条件，农夫约翰希望使用字典序最小的那个。若对某个 $j$，有 $x_i = y_i$ 对所有 $i < j$ 成立且 $x_j < y_j$，则称序列 $x$ 的字典序小于序列 $y$（换言之，两种顺序在某个位置之前完全相同，而在该位置 $x$ 更小）。

请帮助农夫约翰确定最优的挤奶顺序。

输入格式

第一行包含 $N$ 和 $M$。 接下来 $M$ 行每行描述一条观察。第 $i+1$ 行描述第 $i$ 条观察，先给出该观察列表中的奶牛数量 $m_i$，随后给出 $m_i$ 个整数，表示该观察中的奶牛顺序。$\sum m_i$ 最多为 $200,000$。

输出格式

输出 $N$ 个用空格分隔的整数，给出一个 $1 \ldots N$ 的排列，表示农夫约翰应当给奶牛挤奶的顺序。

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

1 4 2 3

提示

这里，农夫约翰有四头奶牛，并且需要满足：1 号牛在 2 号牛之前、2 号牛在 3 号牛之前（第一条观察）；4 号牛在 2 号牛之前（第二条观察）；以及 3 号牛在 4 号牛之前、4 号牛在 1 号牛之前（第三条观察）。前两条观察可以同时满足，但农夫约翰无法同时满足所有这些条件，因为那将要求 1 号牛在 3 号牛之前且 3 号牛在 1 号牛之前。 这意味着有两种可能的顺序：1 4 2 3 和 4 1 2 3，其中第一种字典序更小。 题目致谢：Jay Leeds

标签: USACO|2018|Gold

来源

USACO|2018|Gold