请注意,阿帕土地上的女孩真的很有吸引力。
Arpa 喜欢通宵派对。在其中一场聚会的中间,迈赫达突然出现。他看到n对朋友围坐在一张桌子旁。第i对由一个男孩组成,坐在第i张椅子上,他的女朋友坐在第张椅子上。椅子按顺时针方向编号为 1 到 2n。每张椅子上都坐着一个人。
有两种食物:Kooft 和 Zahre-mar。现在,梅尔达德想知道是否有办法为客人提供食物:
- 每个人只有一种食物,
- 没有男孩和他的女朋友吃同样类型的食物,
- 连续坐在椅子上的任意三位客人中,有两位吃的是不同类型的食物。请注意,椅子 2n 和 1 被视为连续的。
查找 Mehrdad 问题的答案。如果可能的话,找到一些满足条件的食物种类的排列。
输入
第一行包含一个整数 n (1 ≤ n ≤ 105) — 客人对的数量。
接下来 n 行的第 i 行包含一对整数 ai 和 bi (1 ≤ ai, bi ≤ 2n) – 第 i 对中男孩所坐的椅子编号和他女朋友所坐的椅子编号。保证每张椅子上都坐着一个人。
输出
如果没有解,则打印-1。
否则打印n行,其中第i行应该包含两个整数,代表第i对食物的类型。行中的第一个整数是男孩吃的食物类型,第二个整数是女孩吃的食物类型。如果有人有 Kooft,则打印 1,否则打印 2。
如果有多个解决方案,请打印其中任何一个。
示例
输入 #1
3 1 4 2 5 3 6
输出 #1
1 2 2 1 1 2