시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 33 12 12 42.857%

문제

상근이는 생일 선물로 구간 N개를 받았다. 여기서 말하는 구간이란 수의 구간이며, [A, B]와 같은 구간이다. 구간을 어떻게 선물로 받았는 지는 잘 모르겠지만, 진짜로 그 수학에 나오는 구간이다.

상근이는 자신이 가지고 있는 구간 중에서 아래와 같은 조건을 만족하는 가장 긴 서로 다른 구간의 수열을 찾으려고 한다.

수열에 포함되는 모든 구간은 다음 위치에 있는 구간을 포함해야 한다.

가장 긴 수열을 찾는 프로그램을 작성하시오.

입력

첫째 줄에 구간의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

다음 N개 줄에는 각 구간 [A,B]의 정보 A와 B가 주어진다. (1 ≤ A < B ≤ 1,000,000)

출력

첫째 줄에 수열의 길이 K를 출력한다. 다음 K줄에는 수열에 포함되는 구간을 입력 형식과 같이 한 줄에 하나씩 순서대로 출력한다.

예제 입력

5
10 30
20 40
30 50
10 60
30 40

예제 출력

3
10 60
30 50
30 40

예제 입력 2

3
3 4
2 5
1 6

예제 출력 2

3
1 6
2 5
3 4

예제 입력 3

6
1 4
1 5
1 6
1 7
2 5
3 5

예제 출력 3

5
1 7
1 6
1 5
2 5
3 5

힌트