책 쌓기

$N$권의 책을 책상 위에 여러 무더기로 쌓아올리려고 한다. 책은 높이를 무시할 수 있는 직사각형 모양이며, $i$번째 책의 두 변의 길이는 $A_i$와 $B_i$이다. 책은 반드시 가로 방향, 세로 방향 중 하나와 나란한 방향으로 놓아야 한다. 즉, 각각의 책은 90도 회전할 수 있다. 또한, 한 무더기에 쌓아올려진 책을 밑에서부터 순서대로 봤을 때 가로 방향의 길이와 세로 방향의 길이가 각각 단조 감소해야 한다. 즉, 두 인접한 책의 가로 혹은 세로 방향의 길이가 같은 경우도 허용한다.

이 조건을 만족하는 방법 중에서 무더기의 개수가 최소가 되는 방법을 찾아라.

첫째 줄에 책의 개수 $N$이 주어진다.

두번째 줄부터 이어지는 $N$개의 줄에 $A_i$와 $B_i$의 값이 공백으로 구분되어 주어진다.

조건을 만족하며 책을 쌓는 방법 중 무더기의 최소 개수를 출력하여라.

• 주어지는 수는 모두 정수이다.
• $1\leq N \leq 200\,000$
• $1 \le i \le N$ 인 각 $i$ 에 대하여: $1\leq A_i, B_i \leq 10^9$