問題文
1 两侧是 4000 有一个正方形的棋盘,上面有一个车。 已放置 N 。 第 i 车是 R_i 行目 C_i 它被放置在柱方格中。
当黑猫Snuke看到这一幕时,他试图移除尽可能少的车,以便每一行和每一列都有尽可能多的车。 我想确保只有 1 块。 Snuke 应该移除多少个车? 另外,找出必须删除哪些车才能达到该数字,以及绝对不能删除哪些车。
制約
- 1≦N≦40000
- 1≦R_i,C_i≦4000
- 同一个方格上放置的车不超过一辆。
入力
输入是按以下格式从标准输入给出的。
N R_1 C_1 R_2 C_2 : R_N C_N
出力
1 在第 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