#42. 【清华集训2017】小Y和二叉树

题目类型:传统型 时间限制:1000 ms 空间限制:512 MiB
输入文件:标准输入 输出文件:标准输出 答案检查器:文本比较

小Y是一个心灵手巧的OIer,她有许多二叉树模型。

小Y的二叉树模型中,每个结点都具有一个编号,小Y把她最喜欢的一个二叉树模型挂在了墙上,树根在最上面,左右子树分别在树根的左下方与右下方,且他们也都满足这样的悬挂规则。为了让这个模型更加美观,小Y选择了一种让这棵二叉树的中序遍历序列最小的悬挂方法。所谓中序遍历最小,就是指中序遍历的结点编号序列的字典序最小。

一天,这个模型不小心被掉在了地上,幸运的是,所有结点和边都没摔坏,但是她想不起这个模型原来是怎么悬挂的了,也就是说:她想不起来树根节点的编号了。

小Y最近忙于准备清华集训,所以没太多时间处理别的事情,她只好找到同样心灵手巧的你帮忙复原她的二叉树模型。

给定小Y的二叉树模型,结点的编号为 $1$ ~ $n$ ,你需要给出其可能的最小的中序遍历,方便小Y更快的摆好她的模型。


输入格式

第一行为一个正整数 $n$ ,表示点的个数。

后接 $n$ 行,每行若干个整数:

第 $i+1$ 行的第一个整数为 $k_i$ ,表示编号为 $i$ 的结点的度数,后接 $k_i$ 个整数 $a_{i,j}$ ,表示编号为 $i$ 的结点与编号为 $a_{i,j}$ 的结点之间有一条边。

同一行输入的相邻两个元素之间,用恰好一个空格隔开。

输出格式

输出共一行, $n$ 个整数,表示字典序最小的中序遍历。


样例一

input

4
3 2 3 4
1 1
1 1
1 1

output

2 1 3 4

explanation

样例的一组最优解如下:

explanation.png

其中结点$4$为根,结点$1$为结点$4$的左儿子,结点$2,3$分别为结点$1$的左右儿子。


限制与约定

本题共20个测试点,每个测试点5分。各个测试点的数据范围如下:

测试点编号$n\leq$$k_i$特殊条件
$1$$5$$1,2,3$
$2$$10$
$3$$15$
$4$$20$
$5$$100$
$6$$1000$
$7$$2000$
$8$$5000$
$9$$1000000$$1,2$结点$i$与结点$i-1$相连
$10$$100000$
$11$$300000$
$12$$1000000$
$13$$100000$$1,3$保证数据随机
$14$$1000000$
$15$$20000$$1,2,3$保证数据随机
$16$$200000$
$17$$100000$
$18$$500000$
$19$$800000$
$20$$1000000$

随机数据的生成方式如下: 对于第13个测试点,从一棵两个结点的树开始,每次随机一个树上的度数为1的结点(即叶结点),并生成两个与之直接相连的结点,直到这棵树上有 $n$ 个结点。显然,在这个测试点中,$n$ 是一个偶数。 对于第15和第16个测试点,从一棵一个结点的树开始,每次随机一个树上的度数不超过2的结点,并生成一个与之直接相连的结点,直到这棵树上有 $n$ 个结点。

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$


提示

我们提供了一个只包含输入和输出功能的程序 binary_sample.cpp。

关于该程序的说明,见 readme.txt。

你可以在答题时使用该程序的代码,也可以不使用,这将与你的得分无关。