← 返回题目列表

Codeforces · 475/F

F. 元宇宙

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

考虑单位单元的无限网格。其中一些细胞是行星。

元宇宙 M = {p1, p2, ..., pk} 是一组行星。假设有一个无限行或列,具有以下两个性质:1)它上面不包含任何元宇宙M的行星pi; 2)该行或该列的两侧都有M的行星。在这种情况下,我们可以将元宇宙 M 转换为两个非空元宇宙 M1 和 M2,其中包含位于该行或列两侧的行星。

无法使用上述操作进行分割的元宇宙称为宇宙。我们执行这样的操作,直到所有元宇宙都变成宇宙。

给定原始元宇宙中行星的位置,找到作为所描述过程的结果的宇宙数量。可以证明,每个宇宙都是唯一标识的,不依赖于分裂的顺序。

输入

输入的第一行包含一个整数n,(1 ≤ n ≤ 105),表示元宇宙中行星的数量。

接下来的 n 行每行包含整数 xi 和 yi,(- 109 ≤ xi, yi ≤ 109),表示第 i 个行星的坐标。所有行星都位于不同的细胞中。

输出

打印生成的 Universe 的数量。

示例

输入 #1

5
0 0
0 2
2 0
2 1
2 2

输出 #1

3

输入 #2

8
0 0
1 0
0 2
0 3
3 0
3 1
2 3
3 3

输出 #2

1

注意

下图描述了第一个测试用例: