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