Wormhole Cycles

Farmer John conducted high‐energy physics experiments over the weekend that went awry, resulting in n distinct wormholes appearing on his farm—which is modeled as a 2D plane. No two wormholes share the same position.

According to his calculations, the wormholes are paired to form \(\frac{n}{2}\) pairs. For example, if wormholes \(A\) and \(B\) are paired, then any object entering wormhole \(A\) will exit from wormhole \(B\) with the same direction, and vice versa.

However, unpleasant consequences might occur. For example, suppose there are two wormhole pairs: \(A(1,1)\) and \(B(3,1)\). If Bessie the cow starts at \((2,1)\) moving in the positive \(x\) direction, she will enter wormhole \(B(3,1)\), exit at \(A(1,1)\), and then eventually reenter \(B\), trapping her in an infinite loop!

Farmer John knows the exact positions of all wormholes. Although he cannot recall Bessie’s starting position, he does know she always starts moving in the positive \(x\) direction. Your task is to help him compute the number of distinct wormhole pairing schemes for which there exists some starting position that will trap Bessie in an infinite cycle.

inputFormat

The first line contains an even integer n (2 \(\leq n \leq 12\)), representing the number of wormholes. Each of the next n lines contains two integers, representing the \(x\) and \(y\) coordinates of a wormhole. All wormhole positions are distinct.

outputFormat

Output a single integer: the number of pairing schemes that lead to an infinite cycle.

sample

4
0 0
1 0
2 0
3 0

2