← 返回题目列表

AtCoder · jag2017summer_day1_i

I. 卢克

中文机器翻译题面 查看原题

問題文

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 辆车都不会被移除。

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