시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 254 73 51 34.694%

문제

한려해상국립공원은 한반도의 남쪽에 있으며, 120km에 걸친 독특한 해양 생태계를 가지고 있다. 공원은 360개 이상의 섬으로 이루어져 있으며, 섬의 크기도 모두 제각각 다르다. 69개의 무인도와 30개의 유인도로 이루어진 아름다운 수로는 바다의 보석과 같다는 찬사를 받는다.

공원 관리자 김상근은 등고선을 이용해 공원 내의 모든 섬의 고도를 조사하려고 한다. 등고선은 해발 고도가 같은 지점을 연결한 곡선이며, 볼록한 닫힌 곡선이다. (그림 1)

한려해상국립공원의 섬을 나타내는 등고선은 서로 겹치지 않으며, 타원과 같은 단순 볼록 곡선이며 닫혀있다. 

컴퓨터는 등고선 지도를 디지털 등고선 지도로 변형해서 사용한다. 디지털 등고선 지도의 등고선은 볼록 직교 다각형 (그림 2) 이다. 직교 다각형이란 모든 변이 수직 또는 수평인 다각형이다. 직교 다각형 P가 볼록이 되려면, P의 모든 내부와 수직선 또는 수평선과의 교점이 비어있거나 선분이어야 한다.

가장 바깥에 있는 등고선은 레벨 1이다. 등고선 c를 둘러싼 등고선의 레벨이 k인 경우에 c의 레벨은 k+1이다. 그림 2에의 지도에서 가장 높은 등고선의 레벨은 5이다.

등고선 n개로 이루어진 디지털 등고선 지도가 주어진다. 이때, 가장 높은 등고선의 레벨을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 등고선의 개수 m(1 ≤ m ≤ 20,000)이 주어진다. 다음 m개 줄에는 각 등고선의 정보를 나타내는 2k+1개의 정수 k, x1, y1, x2, y2, ..., xk, yk (4 ≤ k ≤ 100, 1 ≤ xi, yi ≤ 109) 가 주어진다. k는 볼록 직교 다각형 Q의 꼭짓점의 개수를 나타내며, (xi, yi)는 Q의 꼭짓점을 나타낸다. 꼭짓점은 반시계방향으로 주어진다. 두 볼록 직교 다각형이 겹치는 경우는 없다.

출력

각 테스트 케이스마다 가장 높은 등고선의 레벨을 출력한다.

예제 입력 1

2
5
4 5 3 14 3 14 12 5 12
4 6 4 13 4 13 11 6 11
4 7 5 12 5 12 10 7 10
4 8 6 11 6 11 9 8 9
4 9 7 10 7 10 8 9 8
4
4 10 7 11 7 11 8 10 8
6 3 7 5 7 5 9 6 9 6 12 3 12
6 8 5 9 5 9 6 12 6 12 9 8 9 
10 9 2 9 3 14 3 14 11 7 11 7 8 6 8 6 4 4 4 4 2

예제 출력 1

5
3

힌트

W3sicHJvYmxlbV9pZCI6Ijg4ODkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI0ZjFcdWFjZTBcdWMxMjAgXHVjOWMwXHViM2M0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NWNcdWI4MjRcdWQ1NzRcdWMwYzFcdWFkNmRcdWI5YmRcdWFjZjVcdWM2ZDBcdWM3NDAgXHVkNTVjXHViYzE4XHViM2M0XHVjNzU4IFx1YjBhOFx1Y2FiZFx1YzVkMCBcdWM3ODhcdWM3M2NcdWJhNzAsIDEyMGttXHVjNWQwIFx1YWM3OFx1Y2U1YyBcdWIzYzVcdWQyYjlcdWQ1NWMgXHVkNTc0XHVjNTkxIFx1YzBkZFx1ZDBkY1x1YWNjNFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFjZjVcdWM2ZDBcdWM3NDAgMzYwXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWMxMmNcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVjMTJjXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjNjNCBcdWJhYThcdWI0NTAgXHVjODFjXHVhYzAxXHVhYzAxIFx1YjJlNFx1Yjk3NFx1YjJlNC4gNjlcdWFjMWNcdWM3NTggXHViYjM0XHVjNzc4XHViM2M0XHVjNjQwIDMwXHVhYzFjXHVjNzU4IFx1YzcyMFx1Yzc3OFx1YjNjNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjNTQ0XHViOTg0XHViMmU0XHVjNmI0IFx1YzIxOFx1Yjg1Y1x1YjI5NCBcdWJjMTRcdWIyZTRcdWM3NTggXHViY2Y0XHVjMTFkXHVhY2ZjIFx1YWMxOVx1YjJlNFx1YjI5NCBcdWNjMmNcdWMwYWNcdWI5N2MgXHViYzFiXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjZjVcdWM2ZDAgXHVhZDAwXHViOWFjXHVjNzkwIFx1YWU0MFx1YzBjMVx1YWRmY1x1Yzc0MCBcdWI0ZjFcdWFjZTBcdWMxMjBcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0IFx1YWNmNVx1YzZkMCBcdWIwYjRcdWM3NTggXHViYWE4XHViNGUwIFx1YzEyY1x1Yzc1OCBcdWFjZTBcdWIzYzRcdWI5N2MgXHVjODcwXHVjMGFjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViNGYxXHVhY2UwXHVjMTIwXHVjNzQwIFx1ZDU3NFx1YmMxYyBcdWFjZTBcdWIzYzRcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YzljMFx1YzgxMFx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NWMgXHVhY2UxXHVjMTIwXHVjNzc0XHViYTcwLCBcdWJjZmNcdWI4NWRcdWQ1NWMgXHViMmViXHVkNzhjIFx1YWNlMVx1YzEyMFx1Yzc3NFx1YjJlNC4gKFx1YWRmOFx1YjliYyAxKTxcL3A+XHJcblxyXG48cD5cdWQ1NWNcdWI4MjRcdWQ1NzRcdWMwYzFcdWFkNmRcdWI5YmRcdWFjZjVcdWM2ZDBcdWM3NTggXHVjMTJjXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWI0ZjFcdWFjZTBcdWMxMjBcdWM3NDAgXHVjMTFjXHViODVjIFx1YWNiOVx1Y2U1OFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzAsIFx1ZDBjMFx1YzZkMFx1YWNmYyBcdWFjMTlcdWM3NDAgXHViMmU4XHVjMjFjIFx1YmNmY1x1Yjg1ZCBcdWFjZTFcdWMxMjBcdWM3NzRcdWJhNzAgXHViMmViXHVkNjAwXHVjNzg4XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWNlZjRcdWQ0ZThcdWQxMzBcdWIyOTQgXHViNGYxXHVhY2UwXHVjMTIwIFx1YzljMFx1YjNjNFx1Yjk3YyBcdWI1MTRcdWM5YzBcdWQxMzggXHViNGYxXHVhY2UwXHVjMTIwIFx1YzljMFx1YjNjNFx1Yjg1YyBcdWJjYzBcdWQ2MTVcdWQ1NzRcdWMxMWMgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0LiBcdWI1MTRcdWM5YzBcdWQxMzggXHViNGYxXHVhY2UwXHVjMTIwIFx1YzljMFx1YjNjNFx1Yzc1OCBcdWI0ZjFcdWFjZTBcdWMxMjBcdWM3NDAgXHViY2ZjXHViODVkIFx1YzljMVx1YWQ1MCBcdWIyZTRcdWFjMDFcdWQ2MTUgKFx1YWRmOFx1YjliYyAyKSBcdWM3NzRcdWIyZTQuIFx1YzljMVx1YWQ1MCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NzRcdWI3ODAgXHViYWE4XHViNGUwIFx1YmNjMFx1Yzc3NCBcdWMyMThcdWM5YzEgXHViNjEwXHViMjk0IFx1YzIxOFx1ZDNjOVx1Yzc3OCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NzRcdWIyZTQuIFx1YzljMVx1YWQ1MCBcdWIyZTRcdWFjMDFcdWQ2MTUgUFx1YWMwMCBcdWJjZmNcdWI4NWRcdWM3NzQgXHViNDE4XHViODI0XHViYTc0LCBQXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWIwYjRcdWJkODBcdWM2NDAgXHVjMjE4XHVjOWMxXHVjMTIwIFx1YjYxMFx1YjI5NCBcdWMyMThcdWQzYzlcdWMxMjBcdWFjZmNcdWM3NTggXHVhZDUwXHVjODEwXHVjNzc0IFx1YmU0NFx1YzViNFx1Yzc4OFx1YWM3MFx1YjA5OCBcdWMxMjBcdWJkODRcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWM3YTUgXHViYzE0XHVhZTY1XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWI0ZjFcdWFjZTBcdWMxMjBcdWM3NDAgXHViODA4XHViY2E4IDFcdWM3NzRcdWIyZTQuIFx1YjRmMVx1YWNlMFx1YzEyMCBjXHViOTdjIFx1YjQ1OFx1YjdlY1x1YzJmYyBcdWI0ZjFcdWFjZTBcdWMxMjBcdWM3NTggXHViODA4XHViY2E4XHVjNzc0IGtcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwIGNcdWM3NTggXHViODA4XHViY2E4XHVjNzQwIGsrMVx1Yzc3NFx1YjJlNC4gXHVhZGY4XHViOWJjIDJcdWM1ZDBcdWM3NTggXHVjOWMwXHViM2M0XHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWIxOTJcdWM3NDAgXHViNGYxXHVhY2UwXHVjMTIwXHVjNzU4IFx1YjgwOFx1YmNhOFx1Yzc0MCA1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2NhbnRvdXIyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI3M3B4OyB3aWR0aDo2NDNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWI0ZjFcdWFjZTBcdWMxMjAgblx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViNTE0XHVjOWMwXHVkMTM4IFx1YjRmMVx1YWNlMFx1YzEyMCBcdWM5YzBcdWIzYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YWMwMFx1YzdhNSBcdWIxOTJcdWM3NDAgXHViNGYxXHVhY2UwXHVjMTIwXHVjNzU4IFx1YjgwOFx1YmNhOFx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNGYxXHVhY2UwXHVjMTIwXHVjNzU4IFx1YWMxY1x1YzIxOCBtKDEgJmxlOyBtICZsZTsgMjAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBtXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHViNGYxXHVhY2UwXHVjMTIwXHVjNzU4IFx1YzgxNVx1YmNmNFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgMmsrMVx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggaywgeDxzdWI+MTxcL3N1Yj4sIHk8c3ViPjE8XC9zdWI+LCB4PHN1Yj4yPFwvc3ViPiwgeTxzdWI+MjxcL3N1Yj4sIC4uLiwgeDxzdWI+azxcL3N1Yj4sIHk8c3ViPms8XC9zdWI+ICg0ICZsZTsgayAmbGU7IDEwMCwgMSAmbGU7IHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD45PFwvc3VwPikgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4ga1x1YjI5NCBcdWJjZmNcdWI4NWQgXHVjOWMxXHVhZDUwIFx1YjJlNFx1YWMwMVx1ZDYxNSBRXHVjNzU4IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViYTcwLCAoeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+KVx1YjI5NCBRXHVjNzU4IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc0MCBcdWJjMThcdWMyZGNcdWFjYzRcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTAgXHViY2ZjXHViODVkIFx1YzljMVx1YWQ1MCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NzQgXHVhY2I5XHVjZTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVhYzAwXHVjN2E1IFx1YjE5Mlx1Yzc0MCBcdWI0ZjFcdWFjZTBcdWMxMjBcdWM3NTggXHViODA4XHViY2E4XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jYW50b3VyMy5wbmdcIiBzdHlsZT1cImhlaWdodDoyMjdweDsgd2lkdGg6NTkzcHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijg4ODkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb250b3VyIE1hcHMiLCJkZXNjcmlwdGlvbiI6IjxwPkhhbGx5ZW9oYWVzYW5nIG5hdGlvbmFsIHBhcmsgaXMgbG9jYXRlZCBpbiB0aGUgc291dGggb2YgdGhlIEtvcmVhbiBQZW5pbnN1bGEuIEhhbGx5ZW9oYWVzYW5nIGlzIGEgdW5pcXVlIG1hcmluZSBlY29zeXN0ZW0gd2hpY2ggZXh0ZW5kcyBhbG9uZyAxMjBrbS4gVGhlIHBhcmsgaXMgc3R1ZGRlZCB3aXRoIG1vcmUgdGhhbiAzNjAgaXNsYW5kcywgbGFyZ2UgYW5kIHNtYWxsLiBTcGVjaWFsbHksIEhhbGx5ZW9zdWRvIHdoaWNoIGlzIGtub3duIGFzIHRoZSBtb3N0IGJlYXV0aWZ1bCB3YXRlcndheSBldmVyIGhhcyA2OSB1bmluaGFiaXRlZCBpc2xhbmRzIGFuZCAzMCBpbmhhYml0ZWQgaXNsYW5kcyBzcHJlYWQgb3V0IGFjcm9zcyB0aGUgc2VhIGxpa2UgamV3ZWxzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Nci4gS2ltLCBhIHBhcmsgc3VwZXJpbnRlbmRlbnQsIHBsYW5zIHRvIGNvbmR1Y3QgYSBzdXJ2ZXkgYWJvdXQgdGhlIGVsZXZhdGlvbnMgb2YgYWxsIGlzbGFuZHMgb2YgdGhlIHBhcmsuIEhlIGhhcyBjb250b3VyIG1hcHMgb2YgdGhlIGlzbGFuZHMuIEEgY29udG91ciBtYXAgc2hvd3MgZWxldmF0aW9ucyBhYm92ZSBzZWEgbGV2ZWwgYW5kIHN1cmZhY2UgZmVhdHVyZXMgb2YgdGhlIGxhbmQgYnkgbWVhbnMgb2YgY29udG91ciBsaW5lcy4gQSBjb250b3VyIGxpbmUgaXMgYSBjbG9zZWQgY3VydmUgd2hpY2ggam9pbnMgcG9pbnRzIG9mIGVxdWFsIGVsZXZhdGlvbiBhYm92ZSBhIGdpdmVuIGxldmVsIChzZWUgRmlndXJlIDEpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgY29udG91ciBsaW5lcyBvZiB0aGUgaXNsYW5kcyBpbiB0aGUgcGFyaywgZG8gbm90IGludGVyc2VjdCBlYWNoIG90aGVyLCBhbmQgYXJlIHNpbXBsZSBjb252ZXggY2xvc2VkIGN1cnZlcyBsaWtlIGVsbGlwc2VzLiBJbiBvcmRlciB0byB1c2UgYSBjb21wdXRlciwgaGUgZmlyc3QgY29udmVydGVkIHRoZSBvcmlnaW5hbCBjb250b3VyIG1hcHMgdG8gY29ycmVzcG9uZGluZyBkaWdpdGFsIGNvbnRvdXIgbWFwcy4gSW4gYSBkaWdpdGFsIGNvbnRvdXIgbWFwLCBhIGNvbnRvdXIgbGluZSBpcyByZXByZXNlbnRlZCBhcyB0aGUgYm91bmRhcnkgb2YgYSByZWN0aWxpbmVhciBjb252ZXggcG9seWdvbiAoc2VlIEZpZ3VyZS4gMikuIEEgcmVjdGlsaW5lYXIgcG9seWdvbiBpcyBhIHBvbHlnb24gd2hvc2UgZWRnZXMgYXJlIGVpdGhlciBob3Jpem9udGFsIG9yIHZlcnRpY2FsLiBBIHJlY3RpbGluZWFyIHBvbHlnb24gUCBpcyBjYWxsZWQgY29udmV4IGlmIHRoZSBpbnRlcnNlY3Rpb24gb2YgdGhlIGludGVyaW9yIG9mIFAgYW5kIGEgdmVydGljYWwgb3IgaG9yaXpvbnRhbCBsaW5lIGlzIGVpdGhlciBlbXB0eSBvciBhIGxpbmUgc2VnbWVudC4gQSBsZXZlbCBpcyBhIHByZWRlZmluZWQgbWVhc3VyZSBmb3IgZWxldmF0aW9uLiBUaGUgb3V0ZXJtb3N0IGNvbnRvdXIgbGluZSBpcyBhdCBsZXZlbCAxLiBJZiB0aGUgY2xvc2VzdCBjb250b3VyIGxpbmUgc3Vycm91bmRpbmcgYSBjb250b3VyIGxpbmUgYyBpcyBhdCBsZXZlbCBrLCB0aGVuIGMgaXMgYXQgbGV2ZWwgaysxLiBJbiBGaWd1cmUgMiwgdGhlIGxldmVsIG9mIHRoZSBoaWdoZXN0IGNvbnRvdXIgbGluZSB0aGF0IHdlIGNhbiBzZWUgaW4gdGhlIG1hcCBpcyA1LiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2NhbnRvdXIyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI3M3B4OyB3aWR0aDo2NDNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5HaXZlbiBhIGNvbnRvdXIgbWFwIHdpdGggbiBjb250b3VyIGxpbmVzIHRoYXQgYXJlIHJlcHJlc2VudGVkIGFzIHRoZSBib3VuZGFyaWVzIG9mIHJlY3RpbGluZWFyIGNvbnZleCBwb2x5Z29ucywgd3JpdGUgYSBwcm9ncmFtIHRoYXQgY29tcHV0ZXMgdGhlIGxldmVsIG9mIHRoZSBoaWdoZXN0IGNvbnRvdXIgbGluZSBpbiB0aGUgbWFwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyBhbiBpbnRlZ2VyIG0gKDEgJmxlOyBtICZsZTsgMjAsMDAwKSwgd2hlcmUgbSBpcyB0aGUgbnVtYmVyIG9mIHJlY3RpbGluZWFyIGNvbnZleCBwb2x5Z29ucyByZXByZXNlbnRpbmcgY29udG91ciBsaW5lcywgSW4gdGhlIG5leHQgbSBsaW5lcyBvZiBlYWNoIHRlc3QgY2FzZSwgZWFjaCBsaW5lIGNvbnRhaW5zIDJrKzEgaW50ZWdlcnMgaywgeDxzdWI+MTxcL3N1Yj4sIHk8c3ViPjE8XC9zdWI+LCB4PHN1Yj4yPFwvc3ViPiwgeTxzdWI+MjxcL3N1Yj4sIC4uLiwgeDxzdWI+azxcL3N1Yj4sIGFuZCB5PHN1Yj5rPFwvc3ViPiAoNCAmbGU7IGsgJmxlOyAxMDAsIDEgJmxlOyB4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4gJmxlOyAxMDxzdXA+OTxcL3N1cD4pLCB3aGVyZSBrIGlzIHRoZSBudW1iZXIgb2YgdmVydGljZXMgb2YgYSByZWN0aWxpbmVhciBjb252ZXh0IHBvbHlnb24gUSBhbmQgKHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPikmIzM5O3MgYXJlIGNvb3JkaW5hdGVzIG9mIGsgdmVydGljZXMgb2YgUSwgd2hpY2ggYXJlIGluIGNvdW50ZXJjbG9ja3dpc2Ugb3JkZXIuIE5vdGljZSB0aGF0IHRoZSBib3VuZGFyaWVzIG9mIGFueSB0d28gcmVjdGlsaW5lYXIgY29udmV4IHBvbHlnb25zIGRvIG5vdCBpbnRlcnNlY3QgZWFjaCBvdGhlcnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiBhbiBpbnRlZ2VyLCB0aGUgbGV2ZWwgb2YgdGhlIGhpZ2hlc3QgY29udG91ciBsaW5lIGluIHRoZSBtYXAuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY2FudG91cjMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjI3cHg7IG9wYWNpdHk6MC45OyB3aWR0aDo1OTNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMy4gSWxsdXN0cmF0aW9ucyBmb3IgU2FtcGxlIElucHV0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2012 B번