Minimum Cuts to Slice All Ropes

After learning Tai Chi, Bob asks Alice to teach him the Tai Chi sword. However, Alice tells him that before learning the sword, he must pass a basic sword test. In the test, Bob is given n ropes. Each rope has two endpoints that are all distinct. The endpoints are tied on a circle and are equally spaced. We label the endpoints in clockwise order from \(1\) to \(2n\).

In each move, Bob makes a straight‐line cut (a line passing through the center of the circle) that cuts every rope whose interior is intersected by the line. In other words, a single cut (which is a diameter) will cut a rope if and only if its two endpoints lie on opposite sides of the line. Bob wonders: what is the minimum number of cuts required to cut all the ropes?

More formally, let each endpoint \(i\) (\(1\le i\le 2n\)) correspond to an angle \(\theta_i=\frac{(i-1)\pi}{n}\) (so the full circle is \(2\pi\)). A rope connecting endpoints \(a\) and \(b\) (given as input) is cut by a line whose direction is determined by an angle \(\varphi\) (where \(0\le\varphi<\pi\)) if and only if

[ \sin((\theta_a-\varphi))\cdot\sin((\theta_b-\varphi))<0. ]

It can be shown that for any set of ropes (i.e. a perfect matching among the \(2n\) endpoints) two cuts always suffice. In some cases one diameter (one cut) is enough. Your task is to determine the minimum number of cuts Bob must make.

Note: The answer is always either 1 or 2.

inputFormat

The first line contains an integer \(n\) (the number of ropes). Each of the following \(n\) lines contains two distinct integers \(a\) and \(b\) (\(1\le a,b\le2n\)) representing the endpoints of a rope. It is guaranteed that all endpoints are distinct.

outputFormat

Output a single integer: the minimum number of cuts required (either 1 or 2).

sample

2
1 2
3 4

1