問題文

$1$ 辺が $4000$ マスのチェス盤があり、その上にルークが $N$ 置かれています。 $i$ 番目のルークは $R_i$ 行目 $C_i$ 列目のマスに置かれています。

それを見た黒猫のスヌケ君は出来るだけ少ない個数のルークを取り除くことによって、どの行や列にもルークが高々 $1$ 個しかないようにしたいと考えました。 スヌケ君はいくつのルークを取り除けばいいでしょうか？ また、その個数を達成するために必ず取り除かなければいけないルーク、絶対に取り除いてはいけないルークがどれなのかも求めてください。

制約

• $1≦N≦40000$
• $1≦R_i,C_i≦4000$
• 同じマスに複数のルークが置かれていることはない

入力

入力は以下の形式で標準入力から与えられる。

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

出力

$1$ 行目には取り除くルークの最小個数を出力せよ。 さらに、続く $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

取り除く個数が最小になるようなルークの取り除き方は下図のような $2$ 通りが考えられますが、 $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