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

Note that girls in Arpa’s land are really attractive.

Arpa loves overnight parties. In the middle of one of these parties Mehrdad suddenly appeared. He saw n pairs of friends sitting around a table. i-th pair consisted of a boy, sitting on the a__i-th chair, and his girlfriend, sitting on the b__i-th chair. The chairs were numbered 1 through 2_n_ in clockwise direction. There was exactly one person sitting on each chair.

There were two types of food: Kooft and Zahre-mar. Now Mehrdad wonders, was there any way to serve food for the guests such that:

• Each person had exactly one type of food,
• No boy had the same type of food as his girlfriend,
• Among any three guests sitting on consecutive chairs, there was two of them who had different type of food. Note that chairs 2_n_ and 1 are considered consecutive.

Find the answer for the Mehrdad question. If it was possible, find some arrangement of food types that satisfies the conditions.

注意：Arpa 的国度里的女孩们非常迷人。

Arpa 热爱通宵派对。在某次派对进行到一半时，Mehrdad 突然现身。他看到有 $ n $ 对情侣围坐在一张圆桌旁。第 $ i $ 对情侣由一名男孩和其女友组成，男孩坐在第 $ a_i $ 号椅子上，女友坐在第 $ b_i $ 号椅子上。椅子按顺时针方向编号为 $ 1 $ 至 $ 2n $。每张椅子上恰好坐了一个人。

现场有两种食物：Kooft 和 Zahre-mar。现在 Mehrdad 想知道：是否存在一种给宾客分发食物的方式，使得满足以下条件：

• 每个人恰好获得一种食物；
• 任意一对情侣（即每个男孩与其女友）所获得的食物种类不同；
• 在任意三张连续的椅子上的宾客中，至少有两人获得的食物种类不同。注意：椅子编号 $ 2n $ 与 $ 1 $ 被视为相邻（即圆桌结构）。

请回答 Mehrdad 提出的问题。若存在满足条件的食物分配方案，请给出其中一种具体安排。

The first line contains an integer n (1  ≤  n  ≤  105) — the number of pairs of guests.

The i-th of the next n lines contains a pair of integers a__i and b__i (1  ≤ a__i, b__i ≤  2_n_) — the number of chair on which the boy in the i-th pair was sitting and the number of chair on which his girlfriend was sitting. It's guaranteed that there was exactly one person sitting on each chair.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 表示宾客对的数量。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq 2n$）—— 分别表示第 $i$ 对宾客中男生所坐的椅子编号和其女友所坐的椅子编号。保证每把椅子上恰好坐了一个人。

If there is no solution, print -1.

Otherwise print n lines, the i-th of them should contain two integers which represent the type of food for the i-th pair. The first integer in the line is the type of food the boy had, and the second integer is the type of food the girl had. If someone had Kooft, print 1, otherwise print 2.

If there are multiple solutions, print any of them.

如果没有解，输出 -1。

否则输出 n 行，其中第 i 行应包含两个整数，表示第 i 对情侣所吃的食物种类。该行的第一个整数表示男孩所吃的食物种类，第二个整数表示女孩所吃的食物种类。若某人吃了 Kooft，则输出 1；否则输出 2。

如果存在多个解，输出任意一个即可。