Problem Description

There is a chessboard with 4000 squares on each side, and there are $ N $ rooks placed on it. The $ i $ -th rook is placed on the square in row $ R_i $ and column $ C_i $.

Seeing this, the black cat Snuke wants to remove as few rooks as possible to ensure that at most one rook is in each row and column. How many rooks does Snuke need to remove? Also, determine which rooks must be removed and which must not be removed to achieve this number.

Input Format

The input is given from the standard input in the following format:

$ N $ $ R_1 $ $ C_1 $ $ R_2 $ $ C_2 $ $ : $ $ R_N $ $ C_N $

Output Format

On the first line, output the minimum number of rooks to remove. Furthermore, for the next $ N $ lines, output the following values for the $ i $ -th rook:

• $ 1 $ if the $ i $ -th rook must be removed,
• $ -1 $ if the $ i $ -th rook must not be removed,
• $ 0 $ otherwise.

Sample Input and Output

Sample Input #1

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

Sample Output #1

3
0
0
0
1
0
-1

Sample Input #2

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

Sample Output #2

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

Notes/Hints

Constraints

• $ 1≦N≦40000 $
• $ 1≦R_i,C_i≦4000 $
• No multiple rooks are placed on the same square.

Sample Explanation 1

There are two possible ways to remove the minimum number of rooks as shown in the figure below, but in both cases, the 4th rook is removed and the 6th rook is not removed.

见题面 Input 部分

见题面 Output 部分