大样例下载

题目描述

一棵二叉树含有 $n$ 个结点，编号为 $1$ ~ $n$。我们只知道每条边连接的是哪两个结点，却不知道这两个结点谁是父亲，谁是儿子。

现在让你确定这棵二叉树的一种可能形态，使得对它进行中序遍历得到的序列字典序最小。

你只需要输出可以得到的字典序最小的中序遍历序列。

输入格式

第一行：一个整数 $n$ ，表示二叉树的结点个数。

接下来的 $n$ 行：

• 其中第 $i（1 ≤ i ≤ n）$ 行首先是一个整数 $k_i（1 ≤ k_i ≤ 3）$，表示与结点 $i$ 相邻的结点个数，然后是 $k_i$ 个整数 $X_{ij}（1 ≤ j ≤ k_i, 1 ≤ X_{ij} ≤ n）$，表示与结点 $i$ 相邻的结点编号，即结点 $i$ 与结点 $X_{ij}$ 之间有一条树边。

输出格式

一行，包含 $n$ 个整数，表示你所确定的二叉树的中序遍历序列。

样例输入

4
3 3 2 4
1 1
1 1
1 1

样例输出

2 1 3 4

样例解释

二叉树的形态如下：

数据范围