CF741C Arpa’s overnight party and Mehrdad’s silent entering

Arpa 所在国度的女孩们非常迷人。

Arpa 喜欢过夜派对。在一次派对的进行中， Mehrdad 突然出现了。他看到有 $ n $ 对朋友围坐在一张圆桌旁。一对朋友由一个男孩和一个女孩组成。第 $ i $ 对朋友中，男孩坐在第 $ a_i $ 个椅子上，女孩坐在第 $ b_i $ 个椅子上。椅子按顺时针方向编号为 $ 1 $ 到 $ 2n $。每个椅子上恰好坐着一个人。  有两种食物：Kooft 和 Zahre-mar。现在 Mehrdad 想知道，是否存在一种为客人分配食物的方式，使得： - 每个人都恰好得到一种食物， - 任何一对男女朋友不能得到同一种食物， - 任意三个坐在连续椅子上的客人中，至少有两个人得到的食物不同。注意椅子 $ 2n $ 和 $ 1 $ 也被视为连续的。 请帮助 Mehrdad 回答这个问题。如果存在方案，请找出一种满足条件的食物分配方案。

第一行包含一个整数 $ n $（$ 1 \le n \le 10^5 $）—— 客人的朋友对数。 接下来的 $ n $ 行中，第 $ i $ 行包含一对整数 $ a_i $ 和 $ b_i $（$ 1 \le a_i, b_i \le 2n $）—— 第 $ i $ 对朋友中男孩所坐的椅子编号和女孩所坐的椅子编号。保证每个椅子上恰好坐着一个人。

如果无解，输出 `-1`。 否则输出 $ n $ 行，第 $ i $ 行应包含两个整数，表示第 $ i $ 对情侣的食物类型。该行第一个整数表示男孩的食物类型，第二个整数表示女孩的食物类型。如果某人吃 Kooft，输出 `1`，否则输出 `2`。 如果存在多组解，输出任意一组即可。

由 deepseek 翻译，人工完善