I - ルーク Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

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 番目のルークはいずれにおいても取り除かれていません。

8e0ee23b7ecee60f72885491dcc28a04.png

入力例 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