Vivoparc 是位于瓦伦西亚的一座动物园。它最近增加了一个由大片平原稀树草原组成的新区域，并被划分为若干个围栏。

我们的目标是为每个新的 Vivoparc 围栏分配 4 种不同物种（狮子、豹子、老虎和黑豹）中的一种动物。由于这些动物领地意识很强，因此我们必须确保没有任何动物能从其所在的围栏看到同物种的其他动物。Vivoparc 的经理向我们发送了一份包含不同围栏之间可见性关系的文件，我们需要为每个围栏分配一个物种。在过程结束时，所有围栏都必须分配有一个物种。

输入格式

输入文件的第一行包含围栏的数量 ($N \le 100$)。接下来的每一行包含一个可见性限制：1-3 表示 1 号围栏中的动物可以看到 3 号围栏中的动物，且 3 号围栏中的动物也可以看到 1 号围栏中的动物。请注意，Vivoparc 的经理工作不太严谨，因此文件中出现的一些数据可能是冗余的。

输出格式

输出文件包含一种可能的物种分配方案。文件包含 $N$ 行，每行包含围栏编号及其分配的物种（1=狮子，2=豹子，3=老虎，4=黑豹）。围栏分配结果必须按编号升序排列。

样例

样例输入 1

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

样例输出 1

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