레이팅 미적용설명
Mirko는 생일 선물로 구간들의 집합을 받았다. 이것으로 할 수 있는 게임이 많다. 그중 하나에서 Mirko는 서로 다른 구간들의 가장 긴 수열을 찾아야 하는데, 수열의 각 구간은 집합에 속해야 하고 각 구간은 수열에서 바로 다음에 오는 구간을 포함해야 한다.
그러한 가장 긴 수열 하나를 찾는 프로그램을 작성하시오.
제약
입력 형식
입력의 첫째 줄에 집합에 있는 구간의 개수인 정수 \(N\) (\(1 \le N \le 100\,000\))이 주어진다.
다음 \(N\)개의 줄에는 구간 하나를 설명하는 두 정수 \(A\)와 \(B\) (\(1 \le A < B \le 1\,000\,000\))가 주어진다.
출력 형식
첫째 줄에 가장 긴 수열의 길이 \(K\)를 출력한다.
다음 \(K\)개의 줄에는 수열의 원소를 하나씩, 입력에 주어진 것과 같은 형식의 구간으로 출력한다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 80점 |
예제 1
입력
3
3 4
2 5
1 6출력
3
1 6
2 5
3 4예제 2
입력
5
10 30
20 40
30 50
10 60
30 40출력
3
10 60
30 50
30 40예제 3
입력
6
1 4
1 5
1 6
1 7
2 5
3 5출력
5
1 7
1 6
1 5
2 5
3 5문제 정보
태그