题目链接

题目描述

有 $2n$ 个人围成一圈坐在桌子边上，每个人占据一个位子，对应这 $2n$ 个人是 $n$ 对情侣，要求情侣不能吃同一种食物，并且桌子上相邻的三个人的食物必须有两个人是不同的，只有两种食物（ $1$ 或者是 $2$ ），问一种可行分配方式。

输入格式

第一行为客人数量

接下来 $n$ 行，第 $i+1$ 行表示第i对情侣男女坐的位置

输出格式

无解输出 -1

否则输出 $n$ 行，第 $i+1$ 行分别为第 $i$ 组男女所食的种类

如果有多组解，输出任意一组解（spj）

样例

3
1 4
2 5
3 6

1 2
2 1
1 2

数据范围

$1\le n\le 10^5$