Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Mystic Carvings

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe 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.

Input

The first line contains integer *n*(3 ≤ *n* ≤ 10^{5}) — 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.

Output

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.

Examples

Input

4

5 4

1 2

6 7

8 3

Output

2

Input

8

1 7

2 4

3 9

5 11

6 8

10 16

13 15

14 12

Output

6

Note

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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/15/2018 06:37:26 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|