问题文

有一个边长为 4000 的棋盘，上面放置了 N 个车（Rook）。第 i 个车被放置在第 Ri 行 Ci 列的格子上。

看到这个情况的黑猫 Snoopy 希望通过尽量少的移除车的数量，使得每一行和每一列最多只能有一个车。Snoopy 需要移除多少个车呢？另外，请找出那些一定要移除的车和不能移除的车。

约束条件

• $1≦N≦40000$
• $1≦R_i,C_i≦4000$
• 同一个格子上不会放置多个车

输入

输入数据从标准输入读取，格式如下：

N R1 C1 R2 C2 : RN CN

输出

在第一行输出需要移除的车的最小数量。接下来的 N 行中，第 i 行输出与第 i 个车相关的信息，具体如下：

• 如果必须移除第 i 个车：1
• 如果绝对不能移除第 i 个车：-1
• 其他情况：0

输入例子 1

6
1 1
1 3
2 1
2 2
2 3
3 2

输出例子 1

3
0
0
0
1
0
-1

为了尽量少移除车的数量，有两种可能的方案如下图所示。然而，第 4 个车在任何方案中都被移除了，而第 6 个车却没有被移除。

输入例子 2

9
1 2
2 2
2 1
3 3
4 6
4 5
4 4
5 4
6 4

输出例子 2

4
-1
1
-1
-1
0
0
1
0
0