시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 57 14 11 35.484%

문제

상근이는 음식점을 개업하려고 한다. 상근이가 살고있는 도시는 크기가 M×M인 격자로 나타낼 수 있다. 따라서, 모든 도로는 수직 또는 수평이고, 각 도로는 0번부터 M-1번까지 번호가 매겨져 있다. 모든 음식점은 수익을 높이기 위해서 교차로에 있다.

도시에는 큰 아파트가 두 개 있고, 두 아파트는 같은 수평 도로 위에 있다. 아래 그림은 도시의 크기가 11×11이며, 동그라미는 현재 있는 음식점, A 또는 B가 쓰여 있는 곳은 아파트를 나타낸다. 아파트에는 이미 레스토랑이 있다. 교차로는 수직 도로와 수평 도로의 쌍을 이용해 좌표로 나타낸다. 두 교차로 (x1, y1)과 (x2, y2)사이의 거리는 |x1-x2| + |y1-y2|이다. 아래 그림에서 A와 B의 좌표는 각각 (0, 5), (10, 5)이다.

상근이는 두 아파트에 사는 사람이 서로 자주 만난다는 것을 알고 있다. 따라서, 새 음식점을 두 아파트의 중간에 만드려고 한다. 하지만, 이미 있는 음식점과 임대비를 생각해보니 무조건 중간에 만든다고 이익이 가장 높은 것은 아니라는 생각이 들었다. 따라서, 아래 조건을 만족하는 "좋은 곳"을 찾으려고 한다. dist(p,q)는 p와 q 사이의 거리이다.

p가 "좋은 곳"이 되려면, 각각의 이미 있는 음식점 q에 대해서, dist(p,A) < dist(q,A) 또는 dist(p,B) < dist(q,B)를 만족해야 한다. 즉, dist(p,A) ≥ dist(q,A) 와 dist(p,B) ≥ dist(q,B)를 만족하는 음식점 q가 있는 경우에 p는 "좋은 곳"이 아니다.

위의 그림에서 (7,4)는 "좋은 곳"이다. 하지만, p=(4,6)은 q=(3,5) 때문에 좋은 곳이 아니다. (dist(p,A) = 5 ≥ dist(q,A) = 3, dist(p,B) = 7 ≥ dist(q,B) = 7) (0,0)도 (0,5) 때문에 좋은 곳이 아니다. 

음식점의 위치가 주어졌을 때, "좋은 곳"의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 도시의 크기 M과 음식점의 수 N이 주어진다. (2 ≤ M ≤ 60,000, 2 ≤ n ≤ 50,000) 다음 줄에는 음식점의 좌표 xi, yi (0 ≤ xi, yi < M)가 주어진다. 두 음식점의 좌표가 같은 경우는 없고, 아파트 A는 첫 번째 음식점, 아파트 B는 두 번째 음식점이 있는 곳에 있다. 또, A와 B는 같은 수평 도로 위에 있다.

출력

각 테스트 케이스마다 "좋은 곳"의 개수를 출력한다.

예제 입력 1

2
6 3
1 3
4 3
0 2
11 11
0 5
10 5
4 9
2 8
7 8
5 6
3 5
5 3
3 2
7 2
9 1

예제 출력 1

2
16
W3sicHJvYmxlbV9pZCI6Ijg5MjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NGNcdWMyZGRcdWM4MTAgXHVhYzFjXHVjNWM1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzRjXHVjMmRkXHVjODEwXHVjNzQ0IFx1YWMxY1x1YzVjNVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWMwYjRcdWFjZTBcdWM3ODhcdWIyOTQgXHViM2M0XHVjMmRjXHViMjk0IFx1ZDA2Y1x1YWUzMFx1YWMwMCBNJnRpbWVzO01cdWM3NzggXHVhY2E5XHVjNzkwXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YmFhOFx1YjRlMCBcdWIzYzRcdWI4NWNcdWIyOTQgXHVjMjE4XHVjOWMxIFx1YjYxMFx1YjI5NCBcdWMyMThcdWQzYzlcdWM3NzRcdWFjZTAsIFx1YWMwMSBcdWIzYzRcdWI4NWNcdWIyOTQgMFx1YmM4OFx1YmQ4MFx1ZDEzMCBNLTFcdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM3NGNcdWMyZGRcdWM4MTBcdWM3NDAgXHVjMjE4XHVjNzc1XHVjNzQ0IFx1YjE5Mlx1Yzc3NFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVhZDUwXHVjYzI4XHViODVjXHVjNWQwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2M0XHVjMmRjXHVjNWQwXHViMjk0IFx1ZDA3MCBcdWM1NDRcdWQzMGNcdWQyYjhcdWFjMDAgXHViNDUwIFx1YWMxYyBcdWM3ODhcdWFjZTAsIFx1YjQ1MCBcdWM1NDRcdWQzMGNcdWQyYjhcdWIyOTQgXHVhYzE5XHVjNzQwIFx1YzIxOFx1ZDNjOSBcdWIzYzRcdWI4NWMgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjJlNC4gXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWIzYzRcdWMyZGNcdWM3NTggXHVkMDZjXHVhZTMwXHVhYzAwIDExJnRpbWVzOzExXHVjNzc0XHViYTcwLCBcdWIzZDlcdWFkZjhcdWI3N2NcdWJiZjhcdWIyOTQgXHVkNjA0XHVjN2FjIFx1Yzc4OFx1YjI5NCBcdWM3NGNcdWMyZGRcdWM4MTAsIEEgXHViNjEwXHViMjk0IEJcdWFjMDAgXHVjNGYwXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWFjZjNcdWM3NDAgXHVjNTQ0XHVkMzBjXHVkMmI4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHVjNTQ0XHVkMzBjXHVkMmI4XHVjNWQwXHViMjk0IFx1Yzc3NFx1YmJmOCBcdWI4MDhcdWMyYTRcdWQxYTBcdWI3OTFcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWFkNTBcdWNjMjhcdWI4NWNcdWIyOTQgXHVjMjE4XHVjOWMxIFx1YjNjNFx1Yjg1Y1x1YzY0MCBcdWMyMThcdWQzYzkgXHViM2M0XHViODVjXHVjNzU4IFx1YzMwZFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzQgXHVjODhjXHVkNDVjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHViNDUwIFx1YWQ1MFx1Y2MyOFx1Yjg1YyAoeDxzdWI+MTxcL3N1Yj4sIHk8c3ViPjE8XC9zdWI+KVx1YWNmYyAoeDxzdWI+MjxcL3N1Yj4sIHk8c3ViPjI8XC9zdWI+KVx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWIyOTQgfHg8c3ViPjE8XC9zdWI+LXg8c3ViPjI8XC9zdWI+fCArIHx5PHN1Yj4xPFwvc3ViPi15PHN1Yj4yPFwvc3ViPnxcdWM3NzRcdWIyZTQuIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWMgQVx1YzY0MCBCXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWFjMDFcdWFjMDEgKDAsIDUpLCAoMTAsIDUpXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2RtYXRscndqYS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMjdweDsgd2lkdGg6MjcycHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjQ1MCBcdWM1NDRcdWQzMGNcdWQyYjhcdWM1ZDAgXHVjMGFjXHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWMxMWNcdWI4NWMgXHVjNzkwXHVjOGZjIFx1YjljY1x1YjA5Y1x1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWMwYzggXHVjNzRjXHVjMmRkXHVjODEwXHVjNzQ0IFx1YjQ1MCBcdWM1NDRcdWQzMGNcdWQyYjhcdWM3NTggXHVjOTExXHVhYzA0XHVjNWQwIFx1YjljY1x1YjRkY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVjNzc0XHViYmY4IFx1Yzc4OFx1YjI5NCBcdWM3NGNcdWMyZGRcdWM4MTBcdWFjZmMgXHVjNzg0XHViMzAwXHViZTQ0XHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YmNmNFx1YjJjOCBcdWJiMzRcdWM4NzBcdWFjNzQgXHVjOTExXHVhYzA0XHVjNWQwIFx1YjljY1x1YjRlMFx1YjJlNFx1YWNlMCBcdWM3NzRcdWM3NzVcdWM3NzQgXHVhYzAwXHVjN2E1IFx1YjE5Mlx1Yzc0MCBcdWFjODNcdWM3NDAgXHVjNTQ0XHViMmM4XHViNzdjXHViMjk0IFx1YzBkZFx1YWMwMVx1Yzc3NCBcdWI0ZTRcdWM1YzhcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjNTQ0XHViNzk4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgJnF1b3Q7XHVjODhiXHVjNzQwIFx1YWNmMyZxdW90O1x1Yzc0NCBcdWNjM2VcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBkaXN0KHAscSlcdWIyOTQgcFx1YzY0MCBxIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxibG9ja3F1b3RlPnBcdWFjMDAgJnF1b3Q7XHVjODhiXHVjNzQwIFx1YWNmMyZxdW90O1x1Yzc3NCBcdWI0MThcdWI4MjRcdWJhNzQsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM3NzRcdWJiZjggXHVjNzg4XHViMjk0IFx1Yzc0Y1x1YzJkZFx1YzgxMCBxXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgZGlzdChwLEEpICZsdDsgZGlzdChxLEEpIFx1YjYxMFx1YjI5NCBkaXN0KHAsQikgJmx0OyBkaXN0KHEsQilcdWI5N2MgXHViOWNjXHVjODcxXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBkaXN0KHAsQSkgJmdlOyBkaXN0KHEsQSkgXHVjNjQwIGRpc3QocCxCKSAmZ2U7IGRpc3QocSxCKVx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjNzRjXHVjMmRkXHVjODEwIHFcdWFjMDAgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMCBwXHViMjk0ICZxdW90O1x1Yzg4Ylx1Yzc0MCBcdWFjZjMmcXVvdDtcdWM3NzQgXHVjNTQ0XHViMmM4XHViMmU0LjxcL2Jsb2NrcXVvdGU+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVhZGY4XHViOWJjXHVjNWQwXHVjMTFjICg3LDQpXHViMjk0ICZxdW90O1x1Yzg4Ylx1Yzc0MCBcdWFjZjMmcXVvdDtcdWM3NzRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgcD0oNCw2KVx1Yzc0MCBxPSgzLDUpIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM4OGJcdWM3NDAgXHVhY2YzXHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC4gKGRpc3QocCxBKSA9IDUgJmdlOyBkaXN0KHEsQSkgPSAzLCBkaXN0KHAsQikgPSA3ICZnZTsgZGlzdChxLEIpID0gNykgKDAsMClcdWIzYzQgKDAsNSkgXHViNTRjXHViYjM4XHVjNWQwIFx1Yzg4Ylx1Yzc0MCBcdWFjZjNcdWM3NzQgXHVjNTQ0XHViMmM4XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM3NGNcdWMyZGRcdWM4MTBcdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsICZxdW90O1x1Yzg4Ylx1Yzc0MCBcdWFjZjMmcXVvdDtcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIzYzRcdWMyZGNcdWM3NTggXHVkMDZjXHVhZTMwIE1cdWFjZmMgXHVjNzRjXHVjMmRkXHVjODEwXHVjNzU4IFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBNICZsZTsgNjAsMDAwLCAyICZsZTsgbiAmbGU7IDUwLDAwMCkgXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3NGNcdWMyZGRcdWM4MTBcdWM3NTggXHVjODhjXHVkNDVjIHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPiAoMCAmbGU7IHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPiAmbHQ7IE0pXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1Yzc0Y1x1YzJkZFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWFjZTAsIFx1YzU0NFx1ZDMwY1x1ZDJiOCBBXHViMjk0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjNzRjXHVjMmRkXHVjODEwLCBcdWM1NDRcdWQzMGNcdWQyYjggQlx1YjI5NCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1Yzc0Y1x1YzJkZFx1YzgxMFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVhY2YzXHVjNWQwIFx1Yzc4OFx1YjJlNC4gXHViNjEwLCBBXHVjNjQwIEJcdWIyOTQgXHVhYzE5XHVjNzQwIFx1YzIxOFx1ZDNjOSBcdWIzYzRcdWI4NWMgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCAmcXVvdDtcdWM4OGJcdWM3NDAgXHVhY2YzJnF1b3Q7XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiODkyMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJlc3RhdXJhbnQiLCJkZXNjcmlwdGlvbiI6IjxwPk1yLiBLaW0gaXMgcGxhbm5pbmcgdG8gb3BlbiBhIG5ldyByZXN0YXVyYW50LiBIaXMgY2l0eSBpcyBsYWlkIG91dCBhcyBhIGdyaWQgd2l0aCBzaXplIE0mdGltZXM7TS4gVGhlcmVmb3JlLCBldmVyeSByb2FkIGlzIGhvcml6b250YWwgb3IgdmVydGljYWwgYW5kIHRoZSBob3Jpem9udGFsIHJvYWRzIChyZXNwLiwgdGhlIHZlcnRpY2FsIHJvYWRzKSBhcmUgbnVtYmVyZWQgZnJvbSAwIHRvIE0tMS4gRm9yIHByb2ZpdGFiaWxpdHksIGFsbCByZXN0YXVyYW50cyBhcmUgbG9jYXRlZCBuZWFyIHJvYWQganVuY3Rpb25zLiBUaGUgY2l0eSBoYXMgdHdvIGJpZyBhcGFydG1lbnRzIHdoaWNoIGFyZSBsb2NhdGVkIG9uIHRoZSBzYW1lIGhvcml6b250YWwgcm9hZC4gVGhlIGZpZ3VyZSBiZWxvdyBzaG93cyBhbiBleGFtcGxlIG9mIGEgY2l0eSBtYXAgd2l0aCBzaXplIDExJnRpbWVzOzExLiBBIGNpcmNsZSByZXByZXNlbnRzIGFuIGV4aXN0aW5nIHJlc3RhdXJhbnQgYW5kIGEgY2lyY2xlIGxhYmVsZWQgd2l0aCAmbHNxdW87QSZyc3F1bzsgb3IgJmxzcXVvO0ImcnNxdW87IHJlcHJlc2VudHMgdGhlIGxvY2F0aW9uIG9mIGFuIGFwYXJ0bWVudC4gTm90aWNlIHRoYXQgYSByZXN0YXVyYW50IGlzIGFscmVhZHkgbG9jYXRlZCBhdCBlYWNoIGFwYXJ0bWVudC4gRWFjaCByb2FkIGp1bmN0aW9uIGlzIHJlcHJlc2VudGVkIGJ5IHRoZSBjb29yZGluYXRlIG9mIHRoZSBvcmRlcmVkIHBhaXIgb2YgYSB2ZXJ0aWNhbCByb2FkIGFuZCBhIGhvcml6b250YWwgcm9hZC4gVGhlIGRpc3RhbmNlIGJldHdlZW4gdHdvIGxvY2F0aW9ucyAoeDEsIHkxKSBhbmQgKHgyLCB5MikgaXMgY29tcHV0ZWQgYXMgfHgxLXgyfCArIHx5MS15MnwuIEluIHRoZSBmaWd1cmUgYmVsb3csIHRoZSBjb29yZGluYXRlcyBvZiBBIGFuZCBCIGFyZSAoMCwgNSkgYW5kICgxMCwgNSksIHJlc3BlY3RpdmVseS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9kbWF0bHJ3amEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjI3cHg7IHdpZHRoOjI3MnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPk1yLiBLaW0ga25vd3MgdGhhdCB0aGUgcmVzaWRlbnRzIG9mIHRoZSB0d28gYXBhcnRtZW50cyBmcmVxdWVudGx5IGhhdmUgYSBtZWV0aW5nLiBTbywgaGUgdGhpbmtzIHRoYXQgdGhlIGJlc3QgbG9jYXRpb24gb2YgYSBuZXcgcmVzdGF1cmFudCBpcyBoYWxmd2F5IGJldHdlZW4gdHdvIGFwYXJ0bWVudHMuIENvbnNpZGVyaW5nIGxlYXNlIGV4cGVuc2VzIGFuZCBleGlzdGluZyByZXN0YXVyYW50cywgaG93ZXZlciwgaGUgY2FuJnJzcXVvO3Qgc2VsZWN0IHRoZSBvcHRpbWFsIGxvY2F0aW9uIHVuY29uZGl0aW9uYWxseS4gSGVuY2UgaGUgZGVjaWRlcyB0byByZWdhcmQgYSBsb2NhdGlvbiBzYXRpc2Z5aW5nIHRoZSBmb2xsb3dpbmcgY29uZGl0aW9uIGFzIGEgZ29vZCBwbGFjZS4gTGV0IGRpc3QocCwgcSkgYmUgdGhlIGRpc3RhbmNlIGJldHdlZW4gcCBhbmQgcS4mbmJzcDs8XC9wPlxyXG5cclxuPGJsb2NrcXVvdGU+QSBsb2NhdGlvbiBwIGlzIGEgZ29vZCBwbGFjZSBpZiBmb3IgZWFjaCBleGlzdGluZyByZXN0YXVyYW50JnJzcXVvO3MgbG9jYXRpb24gcSwgZGlzdChwLCBBKSAmbHQ7IGRpc3QocSwgQSkgb3IgZGlzdChwLCBCKSAmbHQ7IGRpc3QocSwgQikuIEluIG90aGVyIHdvcmRzLCBwIGlzIG5vdCBhIGdvb2QgcGxhY2UgaWYgdGhlcmUgZXhpc3RzIGFuIGV4aXN0aW5nIHJlc3RhdXJhbnQmcnNxdW87cyBsb2NhdGlvbiBxIHN1Y2ggdGhhdCBkaXN0KHAsIEEpICZnZTsgZGlzdChxLCBBKSBhbmQgZGlzdChwLCBCKSAmZ2U7IGRpc3QocSwgQikuJm5ic3A7PFwvYmxvY2txdW90ZT5cclxuXHJcbjxwPkluIHRoZSBhYm92ZSBmaWd1cmUsIHRoZSBsb2NhdGlvbiAoNywgNCkgaXMgYSBnb29kIHBsYWNlLiBCdXQgdGhlIGxvY2F0aW9uIHAgPSAoNCwgNikgaXMgbm90IGdvb2QgYmVjYXVzZSB0aGVyZSBpcyBubyBhcGFydG1lbnQgd2hpY2ggaXMgY2xvc2VyIHRvIHAgdGhhbiB0aGUgcmVzdGF1cmFudCBhdCBxID0gKDMsIDUpLCBpLmUuLCBkaXN0KHAsIEEpID0gNSAmZ2U7IGRpc3QocSwgQSkgPSAzIGFuZCBkaXN0KHAsIEIpID0gNyAmZ2U7IGRpc3QocSwgQikgPSA3LiBBbHNvLCB0aGUgbG9jYXRpb24gKDAsIDApIGlzIG5vdCBnb29kIGR1ZSB0byB0aGUgcmVzdGF1cmFudCBhdCAoMCwgNSkuIE5vdGljZSB0aGF0IHRoZSBleGlzdGluZyByZXN0YXVyYW50cyBhcmUgcG9zaXRpb25lZCByZWdhcmRsZXNzIG9mIE1yLiBLaW0mcnNxdW87cyBjb25kaXRpb24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkdpdmVuIG4gbG9jYXRpb25zIG9mIGV4aXN0aW5nIHJlc3RhdXJhbnRzLCB3cml0ZSBhIHByb2dyYW0gdG8gY29tcHV0ZSB0aGUgbnVtYmVyIG9mIGdvb2QgcGxhY2VzIGZvciBhIG5ldyByZXN0YXVyYW50LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgdGhlIGlucHV0IGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBUIGNhc2VzIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgdHdvIGludGVnZXJzIE0gYW5kIG4gKDIgJmxlOyBNICZsZTsgNjAsMDAwIGFuZCAyICZsZTsgbiAmbGU7IDUwLDAwMCksIHdoaWNoIHJlcHJlc2VudCB0aGUgc2l6ZSBvZiBhIGNpdHkgbWFwIGFuZCB0aGUgbnVtYmVyIG9mIGV4aXN0aW5nIHJlc3RhdXJhbnRzLCByZXNwZWN0aXZlbHkuIFRoZSAoaSsxKS10aCBsaW5lIG9mIGEgdGVzdCBjYXNlIGNvbnRhaW5zIHR3byBpbnRlZ2VycyB4PHN1Yj5pPFwvc3ViPiBhbmQgeTxzdWI+aTxcL3N1Yj4gKGkgPSAxLCAyLCAuLi4gLCBuIGFuZCAwICZsZTsgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+ICZsdDsgTSksIHdoaWNoIHJlcHJlc2VudHMgdGhlIGNvb3JkaW5hdGUgb2YgdGhlIGktdGggZXhpc3RpbmcgcmVzdGF1cmFudC4gQXNzdW1lIHRoYXQgYWxsIHJlc3RhdXJhbnRzIGhhdmUgZGlzdGluY3QgY29vcmRpbmF0ZXMgYW5kIHRoYXQgdGhlIHR3byBhcGFydG1lbnRzIEEgYW5kIEIgYXJlIHBvc2l0aW9uZWQgYXQgdGhlIGxvY2F0aW9ucyBvZiAxLXN0IHJlc3RhdXJhbnQgYW5kIDItbmQgcmVzdGF1cmFudC4gTm90aWNlIHRoYXQgQSBhbmQgQiBhcmUgcGxhY2VkIG9uIHRoZSBzYW1lIGhvcml6b250YWwgbGluZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gUHJpbnQgdGhlIG51bWJlciBvZiBnb29kIHBsYWNlcyB3aGljaCBjYW4gYmUgZm91bmQgaW4gYSBnaXZlbiBjaXR5IG1hcC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2010 I번