인쇄 회로 기판

인쇄 회로 기판에서는 전기가 통하지 않는 판 위에 전도성 배선을 놓는다. 같은 층에 있는 두 도선은 서로 교차하면 합선이 생기므로, 복잡한 경우에는 전도성 판을 여러 층으로 나누고 각 층 사이를 전기가 통하지 않는 재료로 분리한 기판을 사용한다. 그러나 층이 많은 기판일수록 비용이 크기 때문에, 제조사는 필요한 도선들을 가능한 한 적은 수의 층에 배치하려고 한다.

이 문제에서는 모든 도선이 기판의 서로 마주 보는 두 변에 있는 단자를 잇는 기판을 다루며, 필요한 층의 수를 최소로 만드는 것이 목표이다.

아래 그림의 왼쪽에 있는 기판을 생각해 보자. 한 도선이 A와 B를 잇고 다른 도선이 D와 C를 이어야 한다면, 가운데 그림처럼 두 도선을 한 층에 놓을 수 있다. 그러나 A와 C를 잇는 도선과 D와 B를 잇는 도선은 오른쪽 그림처럼 같은 층에 놓을 수 없다.

$W \times H$ 크기의 기판 위에 놓인 $N$개의 도선의 양 끝점 위치가 주어질 때, 모든 도선을 수용하는 데 필요한 최소 층의 수를 구하는 프로그램을 작성하라.

도선의 폭은 단자 사이의 거리에 비해 매우 작다고 가정한다. 즉, 어떤 두 도선 사이에도 항상 세 번째 도선이 지날 공간이 충분히 있다.

첫째 줄에 도선의 수 $N$ ($1 \le N \le 10^5$)이 주어진다. 이어지는 $N$개의 줄에는 각각 두 정수 $X_{i1}$과 $X_{i2}$ ($0 \le X_{ij} \le 10^6$)가 공백으로 구분되어 주어지며, 이는 $i$번째 도선이 점 $(X_{i1}, 0)$과 $(X_{i2}, H)$를 이어야 함을 뜻한다. 입력으로 주어지는 $2N$개의 끝점은 모두 서로 다르다고 가정한다.

필요한 모든 도선을 수용하는 데 필요한 최소 층의 수를 정수 하나로 출력한다.