#P1718. 图形复原

图形复原

题目描述

HWX 小朋友对几何的热爱在电脑组是出了名的,号称“每题必解”,这天,LXC 在玩 logo 的时候突然想到了一个题目,刚好可以去测试一下他封号的虚实,于是,他 logo 编程画了一个 nn 边形,并且将 nn 个顶点用 1,2,3,,n1, 2, 3, \ldots, nnn 个连续自然数随手编了个号,为了增加难度,他又画了一些不相交的对角线。如下图:

他把所有的边和对角线都写在一张纸上,对于上图,他写了:(1,3)(1, 3)(3,2)(3, 2)(2,4)(2, 4)(4,5)(4, 5)(5,1)(5, 1)(1,4)(1, 4)(3,4)(3, 4)。正得意的时候,电脑突然自动重启了,郁闷的是,他忘记保存刚才的 logo 程序了,此刻的他很想利用纸上记录的信息将这个 nn 边形的编号复原,电脑组的你能帮助他吗?

输入格式

第一行 nnn50n \le 50

下面若干行,每行两个数 a,ba, b,表示纸上记录的信息。

输出格式

仅一行,按字典序较小的顺序依次输出顶点的编号。对于上面的例子,你的输出应该是 1 3 2 4 5

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

1 3 2 4 5