시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 221 59 45 34.091%

문제

한려해상국립공원은 한반도의 남쪽에 있으며, 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+XHJcblxyXG48cD5cdWI0ZjFcdWFjZTBcdWMxMjAgblx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViNTE0XHVjOWMwXHVkMTM4IFx1YjRmMVx1YWNlMFx1YzEyMCBcdWM5YzBcdWIzYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWFjMDBcdWM3YTUgXHViMTkyXHVjNzQwIFx1YjRmMVx1YWNlMFx1YzEyMFx1Yzc1OCBcdWI4MDhcdWJjYThcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjRmMVx1YWNlMFx1YzEyMFx1Yzc1OCBcdWFjMWNcdWMyMTggbSgxICZsZTsgbSAmbGU7IDIwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgbVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YjRmMVx1YWNlMFx1YzEyMFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IDJrKzFcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IGssIHg8c3ViPjE8XC9zdWI+LCB5PHN1Yj4xPFwvc3ViPiwgeDxzdWI+MjxcL3N1Yj4sIHk8c3ViPjI8XC9zdWI+LCAuLi4sIHg8c3ViPms8XC9zdWI+LCB5PHN1Yj5rPFwvc3ViPiAoNCAmbGU7IGsgJmxlOyAxMDAsIDEgJmxlOyB4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4gJmxlOyAxMDxzdXA+OTxcL3N1cD4pIFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIGtcdWIyOTQgXHViY2ZjXHViODVkIFx1YzljMVx1YWQ1MCBcdWIyZTRcdWFjMDFcdWQ2MTUgUVx1Yzc1OCBcdWFmMmRcdWM5YzBcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCwgKHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPilcdWIyOTQgUVx1Yzc1OCBcdWFmMmRcdWM5YzBcdWM4MTBcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWFmMmRcdWM5YzBcdWM4MTBcdWM3NDAgXHViYzE4XHVjMmRjXHVhY2M0XHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YmNmY1x1Yjg1ZCBcdWM5YzFcdWFkNTAgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzc0IFx1YWNiOVx1Y2U1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YWMwMFx1YzdhNSBcdWIxOTJcdWM3NDAgXHViNGYxXHVhY2UwXHVjMTIwXHVjNzU4IFx1YjgwOFx1YmNhOFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY2FudG91cjMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjI3cHg7IHdpZHRoOjU5M3B4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI4ODg5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ29udG91ciBNYXBzIiwiZGVzY3JpcHRpb24iOiI8cD5IYWxseWVvaGFlc2FuZyBuYXRpb25hbCBwYXJrIGlzIGxvY2F0ZWQgaW4gdGhlIHNvdXRoIG9mIHRoZSBLb3JlYW4gUGVuaW5zdWxhLiBIYWxseWVvaGFlc2FuZyBpcyBhIHVuaXF1ZSBtYXJpbmUgZWNvc3lzdGVtIHdoaWNoIGV4dGVuZHMgYWxvbmcgMTIwa20uIFRoZSBwYXJrIGlzIHN0dWRkZWQgd2l0aCBtb3JlIHRoYW4gMzYwIGlzbGFuZHMsIGxhcmdlIGFuZCBzbWFsbC4gU3BlY2lhbGx5LCBIYWxseWVvc3VkbyB3aGljaCBpcyBrbm93biBhcyB0aGUgbW9zdCBiZWF1dGlmdWwgd2F0ZXJ3YXkgZXZlciBoYXMgNjkgdW5pbmhhYml0ZWQgaXNsYW5kcyBhbmQgMzAgaW5oYWJpdGVkIGlzbGFuZHMgc3ByZWFkIG91dCBhY3Jvc3MgdGhlIHNlYSBsaWtlIGpld2Vscy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TXIuIEtpbSwgYSBwYXJrIHN1cGVyaW50ZW5kZW50LCBwbGFucyB0byBjb25kdWN0IGEgc3VydmV5IGFib3V0IHRoZSBlbGV2YXRpb25zIG9mIGFsbCBpc2xhbmRzIG9mIHRoZSBwYXJrLiBIZSBoYXMgY29udG91ciBtYXBzIG9mIHRoZSBpc2xhbmRzLiBBIGNvbnRvdXIgbWFwIHNob3dzIGVsZXZhdGlvbnMgYWJvdmUgc2VhIGxldmVsIGFuZCBzdXJmYWNlIGZlYXR1cmVzIG9mIHRoZSBsYW5kIGJ5IG1lYW5zIG9mIGNvbnRvdXIgbGluZXMuIEEgY29udG91ciBsaW5lIGlzIGEgY2xvc2VkIGN1cnZlIHdoaWNoIGpvaW5zIHBvaW50cyBvZiBlcXVhbCBlbGV2YXRpb24gYWJvdmUgYSBnaXZlbiBsZXZlbCAoc2VlIEZpZ3VyZSAxKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGNvbnRvdXIgbGluZXMgb2YgdGhlIGlzbGFuZHMgaW4gdGhlIHBhcmssIGRvIG5vdCBpbnRlcnNlY3QgZWFjaCBvdGhlciwgYW5kIGFyZSBzaW1wbGUgY29udmV4IGNsb3NlZCBjdXJ2ZXMgbGlrZSBlbGxpcHNlcy4gSW4gb3JkZXIgdG8gdXNlIGEgY29tcHV0ZXIsIGhlIGZpcnN0IGNvbnZlcnRlZCB0aGUgb3JpZ2luYWwgY29udG91ciBtYXBzIHRvIGNvcnJlc3BvbmRpbmcgZGlnaXRhbCBjb250b3VyIG1hcHMuIEluIGEgZGlnaXRhbCBjb250b3VyIG1hcCwgYSBjb250b3VyIGxpbmUgaXMgcmVwcmVzZW50ZWQgYXMgdGhlIGJvdW5kYXJ5IG9mIGEgcmVjdGlsaW5lYXIgY29udmV4IHBvbHlnb24gKHNlZSBGaWd1cmUuIDIpLiBBIHJlY3RpbGluZWFyIHBvbHlnb24gaXMgYSBwb2x5Z29uIHdob3NlIGVkZ2VzIGFyZSBlaXRoZXIgaG9yaXpvbnRhbCBvciB2ZXJ0aWNhbC4gQSByZWN0aWxpbmVhciBwb2x5Z29uIFAgaXMgY2FsbGVkIGNvbnZleCBpZiB0aGUgaW50ZXJzZWN0aW9uIG9mIHRoZSBpbnRlcmlvciBvZiBQIGFuZCBhIHZlcnRpY2FsIG9yIGhvcml6b250YWwgbGluZSBpcyBlaXRoZXIgZW1wdHkgb3IgYSBsaW5lIHNlZ21lbnQuIEEgbGV2ZWwgaXMgYSBwcmVkZWZpbmVkIG1lYXN1cmUgZm9yIGVsZXZhdGlvbi4gVGhlIG91dGVybW9zdCBjb250b3VyIGxpbmUgaXMgYXQgbGV2ZWwgMS4gSWYgdGhlIGNsb3Nlc3QgY29udG91ciBsaW5lIHN1cnJvdW5kaW5nIGEgY29udG91ciBsaW5lIGMgaXMgYXQgbGV2ZWwgaywgdGhlbiBjIGlzIGF0IGxldmVsIGsrMS4gSW4gRmlndXJlIDIsIHRoZSBsZXZlbCBvZiB0aGUgaGlnaGVzdCBjb250b3VyIGxpbmUgdGhhdCB3ZSBjYW4gc2VlIGluIHRoZSBtYXAgaXMgNS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jYW50b3VyMi5wbmdcIiBzdHlsZT1cImhlaWdodDoyNzNweDsgd2lkdGg6NjQzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSBjb250b3VyIG1hcCB3aXRoIG4gY29udG91ciBsaW5lcyB0aGF0IGFyZSByZXByZXNlbnRlZCBhcyB0aGUgYm91bmRhcmllcyBvZiByZWN0aWxpbmVhciBjb252ZXggcG9seWdvbnMsIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IGNvbXB1dGVzIHRoZSBsZXZlbCBvZiB0aGUgaGlnaGVzdCBjb250b3VyIGxpbmUgaW4gdGhlIG1hcC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciBtICgxICZsZTsgbSAmbGU7IDIwLDAwMCksIHdoZXJlIG0gaXMgdGhlIG51bWJlciBvZiByZWN0aWxpbmVhciBjb252ZXggcG9seWdvbnMgcmVwcmVzZW50aW5nIGNvbnRvdXIgbGluZXMsIEluIHRoZSBuZXh0IG0gbGluZXMgb2YgZWFjaCB0ZXN0IGNhc2UsIGVhY2ggbGluZSBjb250YWlucyAyaysxIGludGVnZXJzIGssIHg8c3ViPjE8XC9zdWI+LCB5PHN1Yj4xPFwvc3ViPiwgeDxzdWI+MjxcL3N1Yj4sIHk8c3ViPjI8XC9zdWI+LCAuLi4sIHg8c3ViPms8XC9zdWI+LCBhbmQgeTxzdWI+azxcL3N1Yj4gKDQgJmxlOyBrICZsZTsgMTAwLCAxICZsZTsgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjk8XC9zdXA+KSwgd2hlcmUgayBpcyB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIG9mIGEgcmVjdGlsaW5lYXIgY29udmV4dCBwb2x5Z29uIFEgYW5kICh4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4pJiMzOTtzIGFyZSBjb29yZGluYXRlcyBvZiBrIHZlcnRpY2VzIG9mIFEsIHdoaWNoIGFyZSBpbiBjb3VudGVyY2xvY2t3aXNlIG9yZGVyLiBOb3RpY2UgdGhhdCB0aGUgYm91bmRhcmllcyBvZiBhbnkgdHdvIHJlY3RpbGluZWFyIGNvbnZleCBwb2x5Z29ucyBkbyBub3QgaW50ZXJzZWN0IGVhY2ggb3RoZXJzLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gVGhlIGxpbmUgc2hvdWxkIGNvbnRhaW4gYW4gaW50ZWdlciwgdGhlIGxldmVsIG9mIHRoZSBoaWdoZXN0IGNvbnRvdXIgbGluZSBpbiB0aGUgbWFwLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2NhbnRvdXIzLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIyN3B4OyBvcGFjaXR5OjAuOTsgd2lkdGg6NTkzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDMuIElsbHVzdHJhdGlvbnMgZm9yIFNhbXBsZSBJbnB1dC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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