호수

캐나다 남동부, 미국과의 국경 지대에는 "오대호"로 알려진 유명한 다섯 개의 호수가 있다. 이번에 캐나다에서 IOI가 열리게 되면서, 행사장과 가장 가까운 온타리오호에서 관광선을 운항하겠다는 계획이 여러 개 나왔다.

각 관광선 계획은 호수 둘레의 두 지점을 잇는 것이며, 계획은 모두 N개다. i번째 계획은 지점 $s_i$와 지점 $t_i$를 잇는 관광선을 운항하겠다는 것이다. 여기서 지점 $x$란, 호수의 동쪽 끝에서 둘레를 따라 시계 반대 방향으로 거리 $x$미터만큼 간 지점을 뜻한다. 호수의 둘레는 500,000미터다.

이 중에서 가능한 한 많은 계획을 실현하고 싶지만, 배끼리 충돌하는 것을 피하기 위해 두 항로가 교차해서는 안 된다.

N개의 운항 계획이 주어졌을 때, 실현할 수 있는 계획 개수의 최댓값을 구하는 프로그램을 작성하시오.

표준 입력에서 다음 입력을 읽는다.

• 입력의 첫째 줄에는 정수 N이 쓰여 있다. 이는 관광선을 운항하려는 계획의 개수를 나타낸다.
• 입력의 i+1번째 줄 ($1 \le i \le N$)에는 두 정수 $s_i, t_i$가 공백으로 구분되어 쓰여 있다. 이들은 i번째 계획에서 잇게 될 두 지점을 나타낸다. $s_1, \ldots, s_N, t_1, \ldots, t_N$의 총 2N개 값은 모두 서로 다르다.

표준 출력에, 주어진 운항 계획 중 실현할 수 있는 계획 개수의 최댓값을 나타내는 정수 하나를 출력하시오.

• $1 \le N \le 2,000$ (계획의 수)
• $0 \le s_i < 500,000$, $0 \le t_i < 500,000$ (지점의 좌표)

위 입력 예시에 있는 다섯 개의 계획을 나타낸 그림이다 (지점 사이의 간격은 정확하지 않다). 굵은 선으로 표시된 세 개의 계획을 고르면 항로가 교차하지 않게 배를 운항할 수 있다.