관광 열차 좌석 계획

철도 회사에서 일하는 Jim은 새 관광 열차 노선을 계획한다. 계곡을 따라 달리는 이 노선이 큰 인기를 끌 것이라고 확신하지만, 수요가 얼마나 될지는 아직 모른다.

시장 조사 결과로 승객이 이용할 구간의 예상 목록을 받았다. Jim은 이 목록을 바탕으로 수요를 감당하는 데 필요한 최소 좌석 수를 알고 싶다.

승객 수만큼 좌석을 준비하면 비용이 지나치게 커진다. 이용 구간이 겹치지 않는 승객끼리 같은 좌석을 쓰면 비용을 크게 줄일 수 있다.

좌석 배정 방식은 두 가지를 검토한다. 차창 밖 풍경이 좌석 위치에 따라 달라지므로 승객이 좌석을 직접 고를 수 있으면 더 좋다. 정책 1에서는 승객이 예약하는 시점에 아직 비어 있는 좌석 가운데 아무 좌석이나 고를 수 있다. 예약 순서를 알 수 없으므로 필요한 좌석 수를 셀 때는 가능한 모든 순서를 고려해야 한다.

정책 2에서는 승객이 좌석을 고르지 못한다. 예약이 모두 끝난 뒤 철도 운영자가 좌석 배정을 결정한다. 이 방식은 필요한 좌석 수를 크게 줄인다.

두 정책에서 각각 필요한 좌석 수를 계산하는 프로그램을 작성하라.

역이 S1, S2, S3, S4 네 개이고 예상 승객이 p1, p2, p3, p4 네 명인 경우를 보자. p1은 S1에서 S2까지, p2는 S2에서 S3까지, p3은 S1에서 S3까지, p4는 S3에서 S4까지 탄다.

p1과 p2의 구간은 겹치지 않고, p3의 구간은 p1, p2 양쪽과 겹치며, p4의 구간은 누구와도 겹치지 않는다. 한 승객이 내리는 역에서 다른 승객이 타면 두 구간은 노선을 공유하지 않으므로 같은 좌석을 쓸 수 있다.

정책 1에서 좌석 두 개로 충분한지 따져 보자. p1이 먼저 예약하면 두 좌석 중 어느 쪽이든 고를 수 있다. p2가 두 번째로 예약할 때 구간이 p1과 겹치지 않으므로 같은 좌석을 예약해도 되지만, p2에게는 다른 좌석이 더 끌릴 수 있다. p2가 p1과 다른 좌석을 잡으면 S1에서 S3까지 가는 p3에게 남는 좌석이 없다 (그림 I.1).

그림 I.1. 좌석이 두 개일 때

좌석이 세 개면 p1과 p2가 어떻게 예약하든 p3은 좌석을 찾는다. S3과 S4 사이에는 다른 승객이 없으므로 p4도 좌석을 예약한다 (그림 I.2).

그림 I.2. 좌석이 세 개일 때

이 목록에서는 가능한 모든 예약 순서와 좌석 선호를 고려해도 정책 1에 좌석 세 개면 충분하다.

예약이 모두 끝난 뒤 좌석을 배정하면 정책 2에서는 좌석 두 개로 빈틈없이 배정한다 (그림 I.3).

그림 I.3. 좌석 두 개로 빈틈없이 배정한 모습

입력은 다음 형식의 테스트 케이스 하나로 이루어진다.

n
a1 b1
.
.
.
an bn

첫 줄에는 예상 목록에 있는 승객 수 $n$이 주어진다 ($1 \le n \le 200000$). 역은 노선을 따라 1번부터 차례로 번호가 매겨져 있다. 이어지는 $n$개 줄에는 각 승객이 타는 역 번호 $a_i$와 내리는 역 번호 $b_i$가 주어진다 ($1 \le a_i < b_i \le 100000$). 타는 역과 내리는 역이 모두 같은 승객이 여럿 있을 수 있다.

정책 1과 정책 2에서 필요한 좌석 수 $s_1$과 $s_2$를 이 순서대로 한 줄에 공백으로 구분해 출력한다.