시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 128 MB 5 2 2 40.000%

문제

현수는 서강대학교에서 한국사를 강의하는 교수이다. 현수는 총 n개의 역사적 사건을 한 수업시간에 하나씩 강의하려고 한다. 이제, 각 강의에 어떤 역사적 사건을 강의할지 결정하려고 한다.

모든 사건은 발생한 특정 구간 [ai, bi]이 있다. 두 사건이 발생한 구간이 겹치는 경우 두 사건을 연관되었다고 한다. 연관된 사건을 최대한 가까운 시간에 강의하면 학생들의 이해도가 높아진다. 또, 연관된 사건이 아닌 경우에는 일어난 순서를 지키면서 강의해야 한다. 즉, A와 B가 연관된 사건이 아니고, A가 B보다 먼저 일어났다면, A는 B보다 먼저 강의해야 한다.

현수가 강의해야 하는 사건의 구간이 모두 주어졌을 때, 두 연관된 사건이 떨어진 거리의 최대값 k의 최소값을 구하는 프로그램을 작성하시오. i번째 강의와 j번째 강의 사이의 거리는 |i - j|이다

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 50,000)이 주어진다. 다음 n개 줄에는 사건의 구간 ai와 bi가 주어진다. (-109 ≤ ai ≤ bi ≤ 109) 두 구간이 같은 경우는 없다.

출력

각각의 테스트 케이스 마다, 가장 작은 k를 출력한다. 다음 n개 줄에는 강의 순서를 입력과 같은 형식으로 출력한다.

예제 입력 1

1
3
1 6
2 3
4 5

예제 출력 1

1
2 3
1 6
4 5
W3sicHJvYmxlbV9pZCI6Ijk1NDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1ZWRcdWMwYWMgXHVjMmRjXHVhYzA0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ2MDRcdWMyMThcdWIyOTQgXHVjMTFjXHVhYzE1XHViMzAwXHVkNTU5XHVhZDUwXHVjNWQwXHVjMTFjIFx1ZDU1Y1x1YWQ2ZFx1YzBhY1x1Yjk3YyBcdWFjMTVcdWM3NThcdWQ1NThcdWIyOTQgXHVhZDUwXHVjMjE4XHVjNzc0XHViMmU0LiBcdWQ2MDRcdWMyMThcdWIyOTQgXHVjZDFkIG5cdWFjMWNcdWM3NTggXHVjNWVkXHVjMGFjXHVjODAxIFx1YzBhY1x1YWM3NFx1Yzc0NCBcdWQ1NWMgXHVjMjE4XHVjNWM1XHVjMmRjXHVhYzA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWFjMTVcdWM3NThcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWM4MWMsIFx1YWMwMSBcdWFjMTVcdWM3NThcdWM1ZDAgXHVjNWI0XHViNWE0IFx1YzVlZFx1YzBhY1x1YzgwMSBcdWMwYWNcdWFjNzRcdWM3NDQgXHVhYzE1XHVjNzU4XHVkNTYwXHVjOWMwIFx1YWNiMFx1YzgxNVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWMwYWNcdWFjNzRcdWM3NDAgXHViYzFjXHVjMGRkXHVkNTVjIFx1ZDJiOVx1YzgxNSBcdWFkNmNcdWFjMDQgW2E8c3ViPmk8XC9zdWI+LCBiPHN1Yj5pPFwvc3ViPl1cdWM3NzQgXHVjNzg4XHViMmU0LiBcdWI0NTAgXHVjMGFjXHVhYzc0XHVjNzc0IFx1YmMxY1x1YzBkZFx1ZDU1YyBcdWFkNmNcdWFjMDRcdWM3NzQgXHVhY2I5XHVjZTU4XHViMjk0IFx1YWNiZFx1YzZiMCBcdWI0NTAgXHVjMGFjXHVhYzc0XHVjNzQ0IFx1YzVmMFx1YWQwMFx1YjQxOFx1YzVjOFx1YjJlNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzVmMFx1YWQwMFx1YjQxYyBcdWMwYWNcdWFjNzRcdWM3NDQgXHVjZDVjXHViMzAwXHVkNTVjIFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWMyZGNcdWFjMDRcdWM1ZDAgXHVhYzE1XHVjNzU4XHVkNTU4XHViYTc0IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc1OCBcdWM3NzRcdWQ1NzRcdWIzYzRcdWFjMDAgXHViMTkyXHVjNTQ0XHVjOWM0XHViMmU0LiBcdWI2MTAsIFx1YzVmMFx1YWQwMFx1YjQxYyBcdWMwYWNcdWFjNzRcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM3N2NcdWM1YjRcdWIwOWMgXHVjMjFjXHVjMTFjXHViOTdjIFx1YzljMFx1ZDBhNFx1YmE3NFx1YzExYyBcdWFjMTVcdWM3NThcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM5ODksIEFcdWM2NDAgQlx1YWMwMCBcdWM1ZjBcdWFkMDBcdWI0MWMgXHVjMGFjXHVhYzc0XHVjNzc0IFx1YzU0NFx1YjJjOFx1YWNlMCwgQVx1YWMwMCBCXHViY2Y0XHViMmU0IFx1YmEzY1x1YzgwMCBcdWM3N2NcdWM1YjRcdWIwYWNcdWIyZTRcdWJhNzQsIEFcdWIyOTQgQlx1YmNmNFx1YjJlNCBcdWJhM2NcdWM4MDAgXHVhYzE1XHVjNzU4XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNjA0XHVjMjE4XHVhYzAwIFx1YWMxNVx1Yzc1OFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjMGFjXHVhYzc0XHVjNzU4IFx1YWQ2Y1x1YWMwNFx1Yzc3NCBcdWJhYThcdWI0NTAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViNDUwIFx1YzVmMFx1YWQwMFx1YjQxYyBcdWMwYWNcdWFjNzRcdWM3NzQgXHViNWE4XHVjNWI0XHVjOWM0IFx1YWM3MFx1YjlhY1x1Yzc1OCBcdWNkNWNcdWIzMDBcdWFjMTIga1x1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIGlcdWJjODhcdWM5ZjggXHVhYzE1XHVjNzU4XHVjNjQwIGpcdWJjODhcdWM5ZjggXHVhYzE1XHVjNzU4IFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWIyOTQgfGkgLSBqfFx1Yzc3NFx1YjJlNDxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBuICgxICZsZTsgbiAmbGU7IDUwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgblx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGFjXHVhYzc0XHVjNzU4IFx1YWQ2Y1x1YWMwNCBhPHN1Yj5pPFwvc3ViPlx1YzY0MCBiPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgtMTA8c3VwPjk8XC9zdXA+ICZsZTsgYTxzdWI+aTxcL3N1Yj4gJmxlOyBiPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD45PFwvc3VwPikgXHViNDUwIFx1YWQ2Y1x1YWMwNFx1Yzc3NCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWI5YzhcdWIyZTQsIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAga1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7XHViMmU0XHVjNzRjIG5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMxNVx1Yzc1OCBcdWMyMWNcdWMxMWNcdWI5N2MgXHVjNzg1XHViODI1XHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWQ2MTVcdWMyZGRcdWM3M2NcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijk1NDEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIaXN0b3J5IGNvdXJzZSIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSB0byBnaXZlIGEgc2VyaWVzIG9mIGxlY3R1cmVzIG9uIGltcG9ydGFudCBoaXN0b3JpY2FsIGV2ZW50cywgb25lIGV2ZW50IHBlciBsZWN0dXJlLCBpbiBzb21lIG9yZGVyLiBFYWNoIGV2ZW50IGxhc3RlZCBmb3Igc29tZSB0aW1lIGludGVydmFsIFthPHN1Yj5pPFwvc3ViPiwgYjxzdWI+aTxcL3N1Yj5dLiBXZSBzYXkgdGhhdCB0d28gZXZlbnRzIGFyZSByZWxhdGVkIGlmIHRoZWlyIGludGVydmFscyBoYXZlIGEgY29tbW9uIHBvaW50LiBJdCB3b3VsZCBiZSBjb252ZW5pZW50IHRvIHNjaGVkdWxlIGxlY3R1cmVzIG9uIHJlbGF0ZWQgZXZlbnRzIGNsb3NlIHRvIGVhY2ggb3RoZXIuIE1vcmVvdmVyLCBsZWN0dXJlcyBvbiB1bnJlbGF0ZWQgZXZlbnRzIHNob3VsZCBiZSBnaXZlbiBpbiB0aGUgb3JkZXIgaW4gd2hpY2ggdGhlIGV2ZW50cyBoYXZlIHRha2VuIHBsYWNlIChpZiBhbiBldmVudCBBIHByZWNlZGVkIGFuIHVucmVsYXRlZCBldmVudCBCLCB0aGVuIHRoZSBsZWN0dXJlIG9uIEEgc2hvdWxkIHByZWNlZGUgdGhlIGxlY3R1cmUgb24gQikuPFwvcD5cclxuXHJcbjxwPkZpbmQgdGhlIG1pbmltdW0gaW50ZWdlciBrICZnZTsmbmJzcDswIGFuZCBhbiBvcmRlciBvZiB0aGUgbGVjdHVyZXMgc3VjaCB0aGF0IGFueSB0d28gcmVsYXRlZCBldmVudHMgYXJlIHNjaGVkdWxlZCBhdCBtb3N0IGsgbGVjdHVyZXMgYXBhcnQgZnJvbSBlYWNoIG90aGVyIChsZWN0dXJlcyBudW1iZXIgaSBhbmQgaiBhcmUgY29uc2lkZXJlZCB0byBiZSB8aSAmbWludXM7IGp8IGxlY3R1cmVzIGFwYXJ0KS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVC4gVGhlIGRlc2NyaXB0aW9ucyBvZiB0aGUgdGVzdCBjYXNlcyBmb2xsb3c6PFwvcD5cclxuXHJcbjxwPlRoZSBcdWZiMDFyc3QgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSBjb250YWlucyB0aGUgbnVtYmVyIG4sIDEgJmxlOyBuICZsZTsgNTAgMDAwLiBFYWNoIG9mIHRoZSBuZXh0IG4gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzIGE8c3ViPmk8XC9zdWI+IGFuZCBiPHN1Yj5pPFwvc3ViPiwgJm1pbnVzOzEwPHN1cD45PFwvc3VwPiAmbGU7IGE8c3ViPmk8XC9zdWI+ICZsZTsgYjxzdWI+aTxcL3N1Yj4gJmxlOyAxMDxzdXA+OTxcL3N1cD4gJm5kYXNoOyB0aGUgZW5kcyBvZiB0aGUgaS10aCBpbnRlcnZhbC4gVGhlIGludGVydmFscyBhcmUgcGFpcndpc2UgZGlcdWZiMDBlcmVudC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCB0aGUgYW5zd2VycyB0byB0aGUgdGVzdCBjYXNlcyBpbiB0aGUgb3JkZXIgaW4gd2hpY2ggdGhleSBhcHBlYXIgaW4gdGhlIGlucHV0LiBUaGUgXHVmYjAxcnN0IGxpbmUgb2YgdGhlIGFuc3dlciB0byBlYWNoIHRlc3QgY2FzZSBzaG91bGQgY29udGFpbiB0aGUgbWluaW11bSB2YWx1ZSBvZiBrLiBUaGUgbmV4dCBuIGxpbmVzIHNob3VsZCBsaXN0IHRoZSBpbnRlcnZhbHMgKGluIHRoZSBzYW1lIGZvcm1hdCBhcyBpbiB0aGUgaW5wdXQpIGluIGFuIG9yZGVyIHN1Y2ggdGhhdCBhbnkgdHdvIHJlbGF0ZWQgZXZlbnRzIGFyZSBzY2hlZHVsZWQgYXQgbW9zdCBrIGxlY3R1cmVzIGFwYXJ0LiBSZW1lbWJlciB0byBwdXQgYW55IHVucmVsYXRlZCBpbnRlcnZhbHMgaW4gdGhlIHByb3BlciBvcmRlciE8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=