题目描述

小 Z 在学校里有 $8$ 个无话不谈的好朋友（包括他自己），编号分别是$1 ... 8$。但是就算是只有这么几个好朋友，也要分成好几个小团体。

现在给出 $N$ 个小团体的信息，每个小团体有两个人 $A$ 和 $B$ 。班主任正在给他们重新排座，在他们的强烈要求下，每个小团体的两个人必须要坐在一起，可以以 $AB$ 的方式排布，也可以以 $BA$ 的方式排布。

请帮助班主任求出一种满足所有小团体要求的座位排布顺序。若有多种顺序满足要求，则输出字典序最小的一个答案。也就是说，输出结果中的第一个人的编号需要是所有符合要求的排布顺序中最小的，在第一个编号相同的前提下的全部排布顺序中，第二个编号也应该是最小的，以此类推。

输入格式

输入的第一行包含 $N$ ，表示有多少个小团体。

以下 $N$ 行每行包含两个整数 $A$ ，$B$，表示每个小团体中的两个人的编号。

输出格式

输出 $8$ 行，表示符合题目要求的座位分布。

输入输出样例

3
3 8
5 8
2 4

1
2
4
3
8
5
6
7

提示

$1 \leq N \leq 7$。

数据保证结果存在