9210 - 虫洞

Farmer John 周末进行高能物理实验的结果却适得其反,导致n个虫洞出现在农场上,农场是一个二维平面,没有两个虫洞处于同一位置。 根据他的计算,FJ 知道他的虫洞两两配对,形成n/2对配对。例如,如果A和B的虫洞连接成一对,进入虫洞A的任何物体将从虫洞B出去,方向不变;反之亦然。 然而这可能发生相当令人不快的后果。例如,假设有两个成对的虫洞A(1,1)和B(3,1),Bessie 从 (2,1)开始朝着x正方向移动。Bessie 将进入虫洞B(3,1),从A(1,2)出去,然后再次进入B,困在一个无限循环中! FJ知道他的农场里每个虫洞的确切位置。他知道Bessie 总是向x正方向走进来,虽然他不记得贝茜的当前位置。 请帮助FJ计算有多少种虫洞配对方案,使得存在一个位置,使得Bessie从该位置出发,会被困在一个无限循环中。

输入

第一行一个正整数n,表示虫洞数量。 接下来n行,每行两个整数x,y,表示一个虫洞的坐标。

输出

输出一行一个整数表示答案。

样例

输入

4
0 0
1 0
1 1
0 1

输出

2

提示

说明/提示 数据范围 对于100% 的数据,2≤n≤12,0≤x,y≤10^9。 保证n为偶数。 样例解释 将虫洞编号为1∼4,然后通过将1,2 和3,4匹配,如果Bessie 从 (0,0)到 (1,0)之间的任意位置出发,她会陷入无限循环中。 相似的,在相同的起始点,如果配对是1,3和 2,4贝茜也会陷入循环。(如果贝西从3进去,1出来,她会走向2 ,然后被传送到4,最后又回到3) 仅有1,4和2,3 的配对允许贝茜从任何二维平面上的点向x正方向走,而不出现无限循环。

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题