题目描述

我们有一个如下所示的无限大的六边形网格。最初，所有格子都是白色的。

一个六边形格子可以用两个整数 $i$ 和 $j$ 表示为 $(i,j)$。
格子 $(i,j)$ 与以下 6 个格子相邻:
$(i-1,j-1)$
$(i-1,j)$
$(i,j-1)$
$(i,j+1)$
$(i+1,j)$
$(i+1,j+1)$
小高将 $N$ 个格子 $(X_1,Y_1),(X_2,Y_2),\cdots,(X_N,Y_N)$ 涂成黑色。
请求出黑色格子形成的连通分量的数量。
这里，如果两个黑色格子之间可以通过若干个相邻的黑色格子移动到达，则认为这两个黑色格子属于同一个连通分量。

输入格式

输入按以下格式从标准输入给出:
$N$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_N$ $Y_N$

输出格式

输出所求答案。

样例

6
-1 -1
0 1
0 2
1 0
1 2
2 0

3

4
5 0
4 1
-3 -4
-2 -5

4

5
2 1
2 -1
1 0
3 1
1 -1

1

样例1解释

小高将格子涂黑后，网格如下图所示。

黑色格子形成以下三个连通分量:
(-1,-1)
(1,0),(2,0)
(0,1),(0,2),(1,2)

数据范围

输入中的所有值都是整数
$1 \le N \le 1000$
$|X_i|,|Y_i| \le 1000$
$(X_i,Y_i)$ 两两不同。

来源

• AtCoder ABC269D