Arpa’s overnight party and Mehrdad’s silent entering

## 题目描述 有2n个人围成一圈坐在桌子边上，每个人占据一个位子，对应这2n个人是n对情侣，要求情侣不能吃同一种食物，并且桌子上相邻的三个人的食物必须有两个人是不同的，只有两种食物（1或者是2），问一种可行分配方式。 ## 输入格式 第一行为客人数量 接下来n行，第i+1行表示第i对情侣男女坐的位置 ## 输出格式 无解输出-1 否则输出n行，第i+1行分别为第i组男女所食的种类 如果有多组解，输出任意一组解（spj） 感谢@额冻豆腐 提供的翻译

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 $ 2n $ 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 $ 2n $ 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.

The first line contains an integer $ n $ ( $ 1<=n<=10^{5} $ ) — 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}<=2n $ ) — 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.

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.

3
1 4
2 5
3 6

1 2
2 1
1 2