AT_abc226_d [ABC226D] Teleportation

题目描述

AtCoder国家位于无限多的笛卡尔坐标上。

AtCoder国家有 $N$ 个城镇，编号为 $1,2,...,N$。

镇i位于点$(x_i,y_i)$，没有两个不同编号的镇可以在同一坐标上。 AtCoder国家有过渡魔法 (以下简称魔法）。

魔法由一对整数 $(a,b)$ 标识，如果你在点 $(x,y)$ 并使用魔法 $(a,b)$，你可以穿越到 $(x+a，y+b)$。

有一个伟大的魔术师（以下简称魔法师），他可以选择任何一对整数 $(a,b)$ 并学习魔术 $(a,b)$。 魔法师还可以学习任何数量的不同种类的魔法。

当他想用魔法从一个城市移动到另一个城市时，他决定学习一些魔法，这样他就可以对所有一对 $(i,j)$ 不同的城市进行以下操作。

在你所学的魔法中只选择一种类型的魔法时，就只能重复使用所选的魔法，从城市 $i$ 移动到城市 $j$。

为了满足上述条件，魔法师至少要学会多少种不同的魔法？

输入格式

第 1 行输入一个数 $N$.

第 2 行至第 N+1 行每行输入两个数 $x_i,y_i$

输出格式

输出大魔法师至少需要学习的魔法数。

输入输出样例 #1

输入 #1

3
1 2
3 6
7 4

输出 #1

6

输入输出样例 #2

输入 #2

3
1 2
2 2
4 2

输出 #2

2

输入输出样例 #3

输入 #3

4
0 0
0 1000000000
1000000000 0
1000000000 1000000000

输出 #3

8