← 返回题目列表

AtCoder · kupc2024_d

D. 引爆炸药

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

配点 : 100 点

問題文

京都大学校园内 N 地雷已被放置。处所内 2 当在维度平面上表达时, 第 i 个矿井有坐标 它位于 (X_i,Y_i) 。

地雷爆炸时,与爆炸的地雷相同。 X 与坐标处的矿井相同 Y 该坐标处的地雷会连环爆炸。

你的工作是在你选择的坐标处放置一个新地雷。 1 目标是通过放置并引爆尽可能多的地雷。

找出可引爆的地雷最大数量,包括新放置的地雷。

制約

  • 所有输入均为整数
  • 1 \le N \le 2 \times 10^5
  • |X_i|,|Y_i| \le 10^9

入力

输入是按以下格式从标准输入给出的。

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

打印答案。


入力例 1

4
1 1
2 4
3 3
5 4

出力例 1

4

新地雷 如果放入 (2,1) ,它将成为一个地雷。 1,2,4 也会同时爆炸。


入力例 2

12
-7 3
3 4
8 -5
3 -2
-2 8
-5 -3
4 -5
-5 -3
-6 8
8 -5
-7 -5
-2 -7

出力例 2

9