시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB30212411042.636%

문제

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

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

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

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

입력

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

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

출력

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

예제 입력 1

5
10 30
20 40
30 50
10 60
30 40

예제 출력 1

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
W3sicHJvYmxlbV9pZCI6IjI5OTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwZGRcdWM3N2MiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWMwZGRcdWM3N2MgXHVjMTIwXHViYjNjXHViODVjIFx1YWQ2Y1x1YWMwNCBOXHVhYzFjXHViOTdjIFx1YmMxYlx1YzU1OFx1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjIFx1YjlkMFx1ZDU1OFx1YjI5NCBcdWFkNmNcdWFjMDRcdWM3NzRcdWI3ODAgXHVjMjE4XHVjNzU4IFx1YWQ2Y1x1YWMwNFx1Yzc3NFx1YmE3MCwgW0EsIEJdXHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWFkNmNcdWFjMDRcdWM3NzRcdWIyZTQuIFx1YWQ2Y1x1YWMwNFx1Yzc0NCBcdWM1YjRcdWI1YmJcdWFjOGMgXHVjMTIwXHViYjNjXHViODVjIFx1YmMxYlx1YzU1OFx1YjI5NCBcdWM5YzBcdWIyOTQgXHVjNzk4IFx1YmFhOFx1Yjk3NFx1YWNhMFx1YzljMFx1YjljYywgXHVjOWM0XHVjOWRjXHViODVjIFx1YWRmOCBcdWMyMThcdWQ1NTlcdWM1ZDAgXHViMDk4XHVjNjI0XHViMjk0IFx1YWQ2Y1x1YWMwNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YWQ2Y1x1YWMwNCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWFlMzQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWFkNmNcdWFjMDRcdWM3NTggXHVjMjE4XHVjNWY0XHVjNzQ0IFx1Y2MzZVx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzIxOFx1YzVmNFx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWIyOTQgXHViYWE4XHViNGUwIFx1YWQ2Y1x1YWMwNFx1Yzc0MCBcdWIyZTRcdWM3NGMgXHVjNzA0XHVjZTU4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFkNmNcdWFjMDRcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAwXHVjN2E1IFx1YWUzNCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWQ2Y1x1YWMwNFx1Yzc1OCBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVhZDZjXHVhYzA0IFtBLEJdXHVjNzU4IFx1YzgxNVx1YmNmNCBBXHVjNjQwIEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEEgJmx0OyBCICZsZTsgMSwwMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NCBLXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViMmU0XHVjNzRjIEtcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YjI5NCBcdWFkNmNcdWFjMDRcdWM3NDQgXHVjNzg1XHViODI1IFx1ZDYxNVx1YzJkZFx1YWNmYyBcdWFjMTlcdWM3NzQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyOTk1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUE9LTE9OIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBnb3QgYSBzZXQgb2YgaW50ZXJ2YWxzIGZvciBoaXMgYmlydGhkYXkuIFRoZXJlIGFyZSBtYW55IGdhbWVzIGhlIGNhbiBwbGF5IHdpdGggdGhlbS4gSW4gb25lIG9mIHRoZW0sIE1pcmtvIG11c3QgZmluZCB0aGUgbG9uZ2VzdCBzZXF1ZW5jZSBvZiBkaXN0aW5jdCBpbnRlcnZhbHMgc3VjaCB0aGF0IGVhY2ggaW50ZXJ2YWwgaW4gdGhlIHNlcXVlbmNlIGlzIGluIHRoZSBzZXQgYW5kIHRoYXQgZWFjaCBpbnRlcnZhbCBjb250YWlucyB0aGUgb25lIHRoYXQgZm9sbG93cyBpbiB0aGUgc2VxdWVuY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB3aGljaCBmaW5kcyBvbmUgc3VjaCBsb25nZXN0IHNlcXVlbmNlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDAwMDApLCB0aGUgbnVtYmVyIG9mIGludGVydmFscyBpbiB0aGUgc2V0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgQSBhbmQgQiBkZXNjcmliaW5nIG9uZSBpbnRlcnZhbCAoMSAmbGU7IEEgJmx0OyBCICZsZTsgMTAwMDAwMCkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBsZW5ndGggSyBvZiB0aGUgbG9uZ2VzdCBzZXF1ZW5jZSBvbiB0aGUgZmlyc3QgbGluZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIEsgbGluZXMgc2hvdWxkIGNvbnRhaW4gb25lIGVsZW1lbnQgb2YgdGhlIHNlcXVlbmNlLCBhbiBpbnRlcnZhbCBpbiB0aGUgc2FtZSBmb3JtYXQgaXQgd2FzIGdpdmVuIGluIHRoZSBpbnB1dC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #4 5번