Printed Circuit Board

On a printed circuit board, conductive wires are laid on a non-conductive base. Two conductors on the same layer cannot cross without causing a short circuit, so more complex boards use several conductive layers separated by non-conductive material. Because a board with more layers costs more, manufacturers try to assign the required conductors to layers so that as few layers as possible are used.

In this problem we consider boards on which every conductor connects two ports located on opposite edges of the board, and we want to minimize the number of layers.

Consider the board shown on the left of the figure below. If one conductor must connect A to B and another must connect D to C, both can be placed on a single layer, as shown in the middle. But a conductor connecting A to C together with one connecting D to B cannot share a layer, as shown on the right.

Write a program that, given the endpoints of the $N$ conductors on a $W \times H$ board, determines the minimum number of layers needed to accommodate all of them.

You may assume that the width of a conductor is very small compared with the distances between ports; that is, between any two conductors there is always enough room for a third one.

The first line contains $N$ ($1 \le N \le 10^5$), the number of conductors. Each of the next $N$ lines contains two integers $X_{i1}$ and $X_{i2}$ ($0 \le X_{ij} \le 10^6$), separated by a space, meaning that the $i$-th conductor must connect the points $(X_{i1}, 0)$ and $(X_{i2}, H)$. You may assume that all $2N$ endpoints are distinct.

Print a single integer: the minimum number of layers needed to accommodate all of the required conductors.