北极熊发现了一块巨大的圆形浮冰,上面有一些神秘的雕刻。冰面上刻有n条线。每条线连接冰边界上的两个点(我们将这些点称为端点)。端点沿圆周逆时针编号为 1, 2, ..., 2n。没有两条线共享一个端点。
现在,一组 6 只北极熊(爱丽丝、鲍勃、卡罗尔、戴夫、夏娃、弗兰克)将在端点上建造洞穴。每只北极熊都会建造一个洞穴并居住在里面。没有两只北极熊可以在相同的端点上建造洞穴。爱丽丝和鲍勃是一对迷信的恋人。他们相信这些线条是外星人(或者人类,与北极熊差不多)雕刻的,具有一定的精神力量。因此,他们想在由一条线连接的两个端点上建造洞穴。卡罗尔和戴夫、伊芙和弗兰克也是如此。
两个洞穴 X 和 Y 之间的距离定义为一加上沿着冰的边界从 X 行进到 Y 所需穿过的其他洞穴的最小数量(没有洞穴的端点不计算在内)。
为了保证公平,三对恋人之间的距离必须相同(即Alice和Bob之间的距离、Carol和Dave之间的距离以及Eve和Frank之间的距离相同)。
下图显示了两种不同的配置,其中圆圈上的点是端点。左侧的配置无效。虽然每对恋人(A和B、C和D、E和F)都连接了一条线,但距离要求并没有得到满足。 A和B之间的距离为2(可以从A沿顺时针方向经过F到达B)。 E和F之间的距离也是2。但是C和D之间的距离是1(可以从C逆时针方向走到D,不经过任何其他洞穴)。右侧的配置有效。所有三对都具有相同的距离 1。
数一下按照要求建造洞穴的方式有多少种。如果使用同一组 6 个端点,则两个配置被视为相同。
输入
第一行包含整数 n(3 ≤ n ≤ 105) — 行数。
接下来的n行每行都包含两个整数ai,bi(1≤ai,bi≤2n),这意味着冰上刻有一条线连接第ai和第bi个端点。
保证每个端点恰好接触一条线。
输出
打印建造洞穴的方法数量。
请不要编写 %lld 说明符来读取或写入 С++ 中的 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
4 5 4 1 2 6 7 8 3
输出 #1
2
输入 #2
8 1 7 2 4 3 9 5 11 6 8 10 16 13 15 14 12
输出 #2
6
注意
第二个示例对应于问题陈述中的图形。