题目描述

从前，有一个国际象棋棋盘，但是这个棋盘被 using 模改成了一个奇怪的形状。

using 拿到了一棵大小为 $n$ 的带标号树。为了和【数据删除】下棋，他制作了一个棋盘：
他用这棵树按如下方式生成了一个大小为 $n^2$ 的无标号图当作棋盘：

• 先将所有点排成一个 $n$ 行 $n$ 列的点阵，这些点之间一开始没有边。
• 对于树的每一条边 $(u, v)$ 和 $1\sim n$ 中所有整数 $k$：连接「第 $u$ 行第 $k$ 列」与「第 $v$ 行第 $k$ 列」两个点。
• 对于树的每一条边 $(u, v)$ 和 $1\sim n$ 中所有整数 $k$：连接「第 $k$ 行第 $u$ 列」与「第 $k$ 行第 $v$ 列」两个点。
• 连边过程中，这 $n\times n$ 个点始终保持点阵的 $n$ 行 $n$ 列状态。

using 和【数据删除】下了很久，收摊时 using 发现那棵树弄丢了。【数据删除】已经走了，using 也要去睡觉，于是还原那棵树的任务交给你。

输入格式

• 第一行一个整数 $n$。
• 接下来 $2n(n-1)$ 行，每行两个整数 $u, v$，表示图中的一条边。

输出格式

你需要在输入的图中找到 $n$ 个点，使得这 $n$ 个点的导出子图重新标号为 $1\sim n$ 后，恰好是一棵树（即你还原的树）。
若有多解，输出任意一个解即可。

3
1 3
1 6
1 9
2 6
2 8
2 9
3 7
4 5
4 7
5 6
5 8
6 7

3 4 7

样例解释（节选）

输入图是一个网格图，图中点编号如下：

8 2 9
5 6 1
4 7 3

严格符合条件的答案有 5 6 1、4 7 3、8 2 9、8 5 4、2 6 7、9 1 3。
题目只要求输出一个满足结构的树，因此诸如 8 5 6、1 6 7 这类答案也可以；但 8 5 7、9 6 4 这类答案不被允许。
之后该树可重标号为 $1,2,3$，类似一条链。

数据范围与提示

本题共 20 个测试点，每个测试点 5 分。规模与限制如下（特殊性质：A = 原树是一条链；B = 原树是一朵菊花）：