생일
시간 제한1초메모리 제한128 MB
N개의 구간이 주어질 때, 각 구간이 다음 구간을 포함하도록 서로 다른 구간들을 이어붙인 가장 긴 사슬을 찾아 출력합니다.
문제
상근이는 생일 선물로 N개의 구간을 받았다. 각 구간은 [A, B]처럼 두 정수 A와 B로 표현되는 수의 구간이다.
상근이는 자신이 가진 구간 중에서 가장 긴 수열을 만들고 싶다. 수열에 들어가는 구간들은 모두 서로 달라야 하며, 수열의 각 구간은 바로 다음 위치의 구간을 포함해야 한다. 구간 [A, B]가 구간 [C, D]를 포함한다는 것은 A ≤ C이고 D ≤ B라는 뜻이다.
조건을 만족하는 가장 긴 구간 수열 하나를 구하시오.
입력
첫째 줄에 구간의 수 N이 주어진다. (1 ≤ N ≤ 100,000)
다음 N개 줄에는 각 구간 [A, B]의 정보 A와 B가 주어진다. (1 ≤ A < B ≤ 1,000,000)
출력
첫째 줄에 수열의 길이 K를 출력한다. 이어서 K개의 줄에 수열에 포함된 구간을 순서대로 출력한다. 각 줄은 입력과 같은 형식인 A B로 출력한다.