CF297E.Mystic Carvings

The polar bears have discovered a gigantic circular piece of floating ice with some mystic carvings on it. There are n lines carved on the ice. Each line connects two points on the boundary of the ice (we call these points endpoints). The endpoints are numbered 1, 2, ..., 2_n_ counter-clockwise along the circumference. No two lines share an endpoint.

Now a group of 6 polar bears (Alice, Bob, Carol, Dave, Eve, Frank) are going to build caves on the endpoints. Each polar bear would build a cave and live in it. No two polar bears can build a cave on the same endpoints. Alice and Bob is a pair of superstitious lovers. They believe the lines are carved by aliens (or humans, which are pretty much the same thing to polar bears), and have certain spiritual power. Therefore they want to build their caves on two endpoints which are connected by a line. The same for Carol and Dave, Eve and Frank.

The distance between two caves X and Y is defined as one plus minimum number of other caves one need to pass through in order to travel from X to Y along the boundary of the ice (endpoints without caves are not counted).

To ensure fairness, the distances between the three pairs of lovers have to be the same (that is, the distance between Alice and Bob, the distance between Carol and Dave, and the distance between Eve and Frank are the same).

The figures below show two different configurations, where the dots on the circle are the endpoints. The configuration on the left is not valid. Although each pair of lovers (A and B, C and D, E and F) is connected a line, the distance requirement is not satisfied. The distance between A and B is 2 (one can go from A to B in the clockwise direction passing through F). The distance between E and F is also 2. However, the distance between C and D is 1 (one can go from C to D in the counter-clockwise direction without passing through any other caves). The configuration on the right is valid. All three pairs have the same distance 1.

Count the number of ways to build the caves under the requirements. Two configurations are considered the same if the same set of 6 endpoints are used.

北极熊们发现了一块巨大的圆形浮冰，上面刻有一些神秘的图案。浮冰上共有 $n$ 条线段，每条线段连接浮冰边界上的两个点（我们称这些点为端点）。这些端点沿圆周逆时针方向编号为 $1,\,2,\,\dots,\,2n$。任意两条线段不共享端点。

现在有六只北极熊（爱丽丝、鲍勃、卡罗尔、戴夫、伊芙、弗兰克）将在这些端点上建造洞穴并居住其中。每只北极熊建造一个洞穴，且任意两只北极熊不能在同一个端点上建洞。爱丽丝和鲍勃是一对迷信的情侣：他们相信这些线段是外星人（或人类——对北极熊而言二者几乎无异）所刻，蕴含某种灵性力量。因此，他们希望将自己的洞穴建在由同一条线段所连接的两个端点上；卡罗尔与戴夫、伊芙与弗兰克也作同样要求。

定义两座洞穴 $X$ 与 $Y$ 之间的距离为：沿浮冰边界从 $X$ 到 $Y$ 行进时，所需经过的其他洞穴的最少数量加一（未建洞穴的端点不计入）。

为保证公平，三对情侣之间的距离必须相等（即：爱丽丝与鲍勃之间的距离、卡罗尔与戴夫之间的距离、伊芙与弗兰克之间的距离三者相等）。

下图展示了两种不同配置，其中圆周上的点代表端点。左侧配置不合法：尽管每对情侣（A 与 B、C 与 D、E 与 F）均位于某条线段的两个端点上，但不满足距离相等的要求。A 与 B 的距离为 $2$（顺时针从 A 到 B 需经过 F）；E 与 F 的距离也为 $2$；但 C 与 D 的距离为 $1$（逆时针从 C 到 D 不经过任何其他洞穴）。右侧配置合法：三对情侣的距离均为 $1$。

在满足上述所有要求的前提下，求建造洞穴的方案总数。若两种配置所选的 6 个端点集合完全相同，则视为同一种方案。

The first line contains integer n(3 ≤ n ≤ 105) — the number of lines.

Each of the following n lines contains two integers a__i, b__i (1 ≤ a__i, b__i ≤ 2_n_), which means that there is a line carved on the ice connecting the a__i–th and b__i–th endpoint.

It's guaranteed that each endpoints touches exactly one line.

第一行包含一个整数 $n$（$3 \leq n \leq 10^5$）—— 表示线段的数量。

接下来的 $n$ 行中，每行包含两个整数 $a_i$、$b_i$（$1 \leq a_i,\,b_i \leq 2n$），表示冰面上刻有一条连接第 $a_i$ 个端点与第 $b_i$ 个端点的线段。

保证每个端点恰好属于一条线段。

Print the number of ways to build the caves.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输出建造洞穴的方案数。

请注意，在 C++ 中不要使用 %lld 说明符来读取或写入 64 位整数。推荐使用 cin、cout 流，或 %I64d 说明符。

The second sample corresponds to the figure in the problem statement.

第二个样例对应于题目描述中的图。