Baltic Olympiad in Informatics: 2010 Day 1, Problem 3

In a printed circuit board, conductive wires are laid on a non-conductive board. Because the conductors in the same layer cannot cross without creating short-circuits, boards with conductors divided into several layers separated by non-conductive board material are used in more complex cases. However, boards with more layers are more expensive. So, manufacturers try to allocate the required conductors to layers in a way that minimizes the number of layers needed.

In this task we look at boards where each conductor is connecting two ports located on opposite edges of the board and seek to minimize the cost of such a board.

Consider, for example, the board shown on the left on the figure below. If one conductor has to connect $A$ to $B$ and another $D$ to $C$, this could be achieved in a single layer, as shown in the middle on the figure. But a conductor connecting $A$ to $C$ and another connecting $D$ to $B$ could not be laid out in the same layer, as can be seen on the right on the figure.

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

It may be assumed the width of the conductors is very small compared to the distances between the ports. That is, between any two conductors, there is always enough room for a third one.

Constraints

$1\le N\le {10}^5$

$0\le X_{ij}\le {10}^6$

Input Specification

The first line of input contains $N$, the number of connectors. Each of the following $N$ lines contains two integers, $X_{i1}$ and $X_{i2}$, separated by a space, meaning that the $i^{\text{th}}$ conductor has to connect the points $(X_{i1},0)$ and $(X_{i2},H)$. It may be assumed that all $2N$ endpoints are distinct.

Output Specification

Output a single integer, the minimal number of layers needed to accommodate all the required conductors.

Sample Input 1

2
1 1
3 3

Sample Output 1

1

Sample Input 2

2
1 3
3 1

Sample Output 2

2

Explanation for Sample Output 2

This is the same situation as the rightmost PCB on the image above. $(1,0)$ must be connected to $(3,H)$ but crosses over another circuit. Another layer is required to prevent the crossover.