Description

Farmer John's high-energy physics experiment over the weekend backfired, causing $n$ wormholes to appear on the farm, which is a two-dimensional plane. No two wormholes are at the same position.

According to his calculations, FJ knows the wormholes are paired up, forming $\dfrac{n}{2}$ pairs. For example, if wormholes $A$ and $B$ form a pair, any object entering wormhole $A$ will exit from wormhole $B$ with its direction unchanged, and vice versa.

However, this can lead to a rather unpleasant consequence. For instance, suppose there are two paired wormholes $A(1,1)$ and $B(3,1)$, and Bessie starts at $(2,1)$ moving in the positive $x$ direction. Bessie will enter wormhole $B(3,1)$, exit from $A(1,1)$, then enter $B$ again, getting trapped in an infinite loop!

FJ knows the exact position of every wormhole on his farm. He knows Bessie always moves in the positive $x$ direction, although he does not remember Bessie's current position.

Please help FJ count how many pairing schemes of wormholes have the property that there exists a position such that if Bessie starts there, she will be trapped in an infinite loop.

Input Format

The first line contains a positive integer $n$, the number of wormholes.

Each of the next $n$ lines contains two integers $x, y$, the coordinates of a wormhole.

Output Format

Output a single integer, the answer.

4
0 0
1 0
1 1
0 1

2

Hint

Constraints

For 100% of the testdata, $2 \le n \le 12$, $0 \le x,y \le 10^9$.
It is guaranteed that $n$ is even.

Sample Explanation

Number the wormholes $1$ to $4$. If we pair $1,2$ and $3,4$, then if Bessie starts anywhere between $(0,0)$ and $(1,0)$, she will fall into an infinite loop.

Similarly, with the same starting point, if the pairings are $1,3$ and $2,4$, Bessie will also be trapped in a loop. (If Bessie enters through $3$ and exits from $1$, she will move toward $2$, then be teleported to $4$, and finally return to $3$.)

Only the pairing $1,4$ and $2,3$ allows Bessie to walk in the positive $x$ direction from any point in the plane without entering an infinite loop.

Problem statement translation from NOCOW.

Translated by ChatGPT 5