← 返回题目列表

Codeforces · 741/C

C. 阿尔帕的通宵聚会和迈赫达的沉默进入

中文机器翻译题面 查看原题

请注意,阿帕土地上的女孩真的很有吸引力。

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