该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

一颗包含 $N \ (1 \le N \le 10^6)$ 个顶点无根树（编号为 $1$ ~ $N$），每次操作如下：

找到树中编号最小且度数为1的节点（叶子）$x$，把与 $x$ 相连的节点 $y$ 加入序列，并将该叶子节点 $x$ 及 $x$ 与 $y$ 之间的边删除。

执行以上操作 $N−2$ 次，最终得到的长度为 $N - 2$ 的整数序列就是这棵树的 Prufer 编码。

显然：再执行一次，得到的数一定是 $N$。

你的任务是：根据给定这棵树的邻接表，获得 Prufer 编码。

输入格式

第一行一个整数 $N$。

下来 $N$ 行。

第 $i$ 行 第一个整数 $k_i$，表示节点 $i$ 有 $k_i$ 个点与其相连。下来 $k_i$ 个整数。

输出格式

输出 $N-2$ 个数，表示树的 Prüfer 编码。

示例

输入

6
2 4 6
3 3 5 6
1 2
1 1
1 2
2 1 2

输出

2 1 6 2