AT_jag2017summer_day1_i ルーク

[problemUrl]: https://atcoder.jp/contests/jag2017summer-day1/tasks/jag2017summer_day1_i $ 1 $ 辺が $ 4000 $ マスのチェス盤があり、その上にルークが $ N $ 置かれています。 $ i $ 番目のルークは $ R_i $ 行目 $ C_i $ 列目のマスに置かれています。 それを見た黒猫のスヌケ君は出来るだけ少ない個数のルークを取り除くことによって、どの行や列にもルークが高々 $ 1 $ 個しかないようにしたいと考えました。 スヌケ君はいくつのルークを取り除けばいいでしょうか？ また、その個数を達成するために必ず取り除かなければいけないルーク、絶対に取り除いてはいけないルークがどれなのかも求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ R_1 $ $ C_1 $ $ R_2 $ $ C_2 $ $ : $ $ R_N $ $ C_N $

$ 1 $ 行目には取り除くルークの最小個数を出力せよ。 さらに、続く $ N $ 行のうち $ i $ 行目には、$ i $ 番目のルークに関する以下のような値を出力せよ。 - $ i $ 番目のルークを必ず取り除かなければならない場合： $ 1 $ - $ i $ 番目のルークを絶対に取り除いてはいけない場合： $ -1 $ - それ以外の場合： $ 0 $

### 制約 - $ 1≦N≦40000 $ - $ 1≦R_i,C_i≦4000 $ - 同じマスに複数のルークが置かれていることはない ### Sample Explanation 1 取り除く個数が最小になるようなルークの取り除き方は下図のような $ 2 $ 通りが考えられますが、 $ 4 $ 番目のルークはいずれにおいても取り除かれており、$ 6 $ 番目のルークはいずれにおいても取り除かれていません。 !\[8e0ee23b7ecee60f72885491dcc28a04.png\](https://img.atcoder.jp/jag2017summer-day1/8e0ee23b7ecee60f72885491dcc28a04.png)