시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHViM2M0XHVjMmRjXHVjNWQwXHViMjk0IFx1ZDA3MCBcdWM1NDRcdWQzMGNcdWQyYjhcdWFjMDAgXHViNDUwIFx1YWMxYyBcdWM3ODhcdWFjZTAsIFx1YjQ1MCBcdWM1NDRcdWQzMGNcdWQyYjhcdWIyOTQgXHVhYzE5XHVjNzQwIFx1YzIxOFx1ZDNjOSBcdWIzYzRcdWI4NWMgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjJlNC4gXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWIzYzRcdWMyZGNcdWM3NTggXHVkMDZjXHVhZTMwXHVhYzAwIDExJnRpbWVzOzExXHVjNzc0XHViYTcwLCBcdWIzZDlcdWFkZjhcdWI3N2NcdWJiZjhcdWIyOTQgXHVkNjA0XHVjN2FjIFx1Yzc4OFx1YjI5NCBcdWM3NGNcdWMyZGRcdWM4MTAsIEEgXHViNjEwXHViMjk0IEJcdWFjMDAgXHVjMzY4XHVjNzg4XHViMjk0IFx1YWNmM1x1Yzc0MCBcdWM1NDRcdWQzMGNcdWQyYjhcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWM1NDRcdWQzMGNcdWQyYjhcdWM1ZDBcdWIyOTQgXHVjNzc0XHViYmY4IFx1YjgwOFx1YzJhNFx1ZDFhMFx1Yjc5MVx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YWQ1MFx1Y2MyOFx1Yjg1Y1x1YjI5NCBcdWMyMThcdWM5YzEgXHViM2M0XHViODVjXHVjNjQwIFx1YzIxOFx1ZDNjOSBcdWIzYzRcdWI4NWNcdWM3NTggXHVjMzBkXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWM4OGNcdWQ0NWNcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWI0NTAgXHVhZDUwXHVjYzI4XHViODVjICh4PHN1Yj4xPFwvc3ViPiwgeTxzdWI+MTxcL3N1Yj4pXHVhY2ZjICh4PHN1Yj4yPFwvc3ViPiwgeTxzdWI+MjxcL3N1Yj4pXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWM3MFx1YjlhY1x1YjI5NCB8eDxzdWI+MTxcL3N1Yj4teDxzdWI+MjxcL3N1Yj58ICsgfHk8c3ViPjE8XC9zdWI+LXk8c3ViPjI8XC9zdWI+fFx1Yzc3NFx1YjJlNC4gXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YzVkMFx1YzExYyBBXHVjNjQwIEJcdWM3NTggXHVjODhjXHVkNDVjXHViMjk0IFx1YWMwMVx1YWMwMSAoMCwgNSksICgxMCwgNSlcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZG1hdGxyd2phLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIyN3B4OyB3aWR0aDoyNzJweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViNDUwIFx1YzU0NFx1ZDMwY1x1ZDJiOFx1YzVkMCBcdWMwYWNcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzc0IFx1YzExY1x1Yjg1YyBcdWM3OTBcdWM4ZmMgXHViOWNjXHViMDljXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM1NGNcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzBjOCBcdWM3NGNcdWMyZGRcdWM4MTBcdWM3NDQgXHViNDUwIFx1YzU0NFx1ZDMwY1x1ZDJiOFx1Yzc1OCBcdWM5MTFcdWFjMDRcdWM1ZDAgXHViOWNjXHViNGRjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWM3NzRcdWJiZjggXHVjNzg4XHViMjk0IFx1Yzc0Y1x1YzJkZFx1YzgxMFx1YWNmYyBcdWM3ODRcdWIzMDBcdWJlNDRcdWI5N2MgXHVjMGRkXHVhYzAxXHVkNTc0XHViY2Y0XHViMmM4IFx1YmIzNFx1Yzg3MFx1YWM3NCBcdWM5MTFcdWFjMDRcdWM1ZDAgXHViOWNjXHViNGUwXHViMmU0XHVhY2UwIFx1Yzc3NFx1Yzc3NVx1Yzc3NCBcdWFjMDBcdWM3YTUgXHViMTkyXHVjNzQwIFx1YWM4M1x1Yzc0MCBcdWM1NDRcdWIyYzhcdWI3N2NcdWIyOTQgXHVjMGRkXHVhYzAxXHVjNzc0IFx1YjRlNFx1YzVjOFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWM1NDRcdWI3OTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCAmcXVvdDtcdWM4OGJcdWM3NDAgXHVhY2YzJnF1b3Q7XHVjNzQ0IFx1Y2MzZVx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIGRpc3QocCxxKVx1YjI5NCBwXHVjNjQwIHEgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWM3MFx1YjlhY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPGJsb2NrcXVvdGU+cFx1YWMwMCAmcXVvdDtcdWM4OGJcdWM3NDAgXHVhY2YzJnF1b3Q7XHVjNzc0IFx1YjQxOFx1YjgyNFx1YmE3NCwgXHVhYzAxXHVhYzAxXHVjNzU4IFx1Yzc3NFx1YmJmOCBcdWM3ODhcdWIyOTQgXHVjNzRjXHVjMmRkXHVjODEwIHFcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBkaXN0KHAsQSkgJmx0OyBkaXN0KHEsQSkgXHViNjEwXHViMjk0IGRpc3QocCxCKSAmbHQ7IGRpc3QocSxCKVx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM5ODksIGRpc3QocCxBKSAmZ2U7IGRpc3QocSxBKSBcdWM2NDAgZGlzdChwLEIpICZnZTsgZGlzdChxLEIpXHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWM3NGNcdWMyZGRcdWM4MTAgcVx1YWMwMCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwIHBcdWIyOTQgJnF1b3Q7XHVjODhiXHVjNzQwIFx1YWNmMyZxdW90O1x1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvYmxvY2txdW90ZT5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWMgKDcsNClcdWIyOTQgJnF1b3Q7XHVjODhiXHVjNzQwIFx1YWNmMyZxdW90O1x1Yzc3NFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBwPSg0LDYpXHVjNzQwIHE9KDMsNSkgXHViNTRjXHViYjM4XHVjNWQwIFx1Yzg4Ylx1Yzc0MCBcdWFjZjNcdWM3NzQgXHVjNTQ0XHViMmM4XHViMmU0LiAoZGlzdChwLEEpID0gNSAmZ2U7IGRpc3QocSxBKSA9IDMsIGRpc3QocCxCKSA9IDcgJmdlOyBkaXN0KHEsQikgPSA3KSAoMCwwKVx1YjNjNCAoMCw1KSBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjODhiXHVjNzQwIFx1YWNmM1x1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1Yzc0Y1x1YzJkZFx1YzgxMFx1Yzc1OCBcdWM3MDRcdWNlNThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgJnF1b3Q7XHVjODhiXHVjNzQwIFx1YWNmMyZxdW90O1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWQwNmNcdWFlMzAgTVx1YWNmYyBcdWM3NGNcdWMyZGRcdWM4MTBcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE0gJmxlOyA2MCwwMDAsIDIgJmxlOyBuICZsZTsgNTAsMDAwKSBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc0Y1x1YzJkZFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWMgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+ICgwICZsZTsgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+ICZsdDsgTSlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTAgXHVjNzRjXHVjMmRkXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YWNlMCwgXHVjNTQ0XHVkMzBjXHVkMmI4IEFcdWIyOTQgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM3NGNcdWMyZGRcdWM4MTAsIFx1YzU0NFx1ZDMwY1x1ZDJiOCBCXHViMjk0IFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjNzRjXHVjMmRkXHVjODEwXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWFjZjNcdWM1ZDAgXHVjNzg4XHViMmU0LiBcdWI2MTAsIEFcdWM2NDAgQlx1YjI5NCBcdWFjMTlcdWM3NDAgXHVjMjE4XHVkM2M5IFx1YjNjNFx1Yjg1YyBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0ICZxdW90O1x1Yzg4Ylx1Yzc0MCBcdWFjZjMmcXVvdDtcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI4OTIwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUmVzdGF1cmFudCIsImRlc2NyaXB0aW9uIjoiPHA+TXIuIEtpbSBpcyBwbGFubmluZyB0byBvcGVuIGEgbmV3IHJlc3RhdXJhbnQuIEhpcyBjaXR5IGlzIGxhaWQgb3V0IGFzIGEgZ3JpZCB3aXRoIHNpemUgTSZ0aW1lcztNLiBUaGVyZWZvcmUsIGV2ZXJ5IHJvYWQgaXMgaG9yaXpvbnRhbCBvciB2ZXJ0aWNhbCBhbmQgdGhlIGhvcml6b250YWwgcm9hZHMgKHJlc3AuLCB0aGUgdmVydGljYWwgcm9hZHMpIGFyZSBudW1iZXJlZCBmcm9tIDAgdG8gTS0xLiBGb3IgcHJvZml0YWJpbGl0eSwgYWxsIHJlc3RhdXJhbnRzIGFyZSBsb2NhdGVkIG5lYXIgcm9hZCBqdW5jdGlvbnMuIFRoZSBjaXR5IGhhcyB0d28gYmlnIGFwYXJ0bWVudHMgd2hpY2ggYXJlIGxvY2F0ZWQgb24gdGhlIHNhbWUgaG9yaXpvbnRhbCByb2FkLiBUaGUgZmlndXJlIGJlbG93IHNob3dzIGFuIGV4YW1wbGUgb2YgYSBjaXR5IG1hcCB3aXRoIHNpemUgMTEmdGltZXM7MTEuIEEgY2lyY2xlIHJlcHJlc2VudHMgYW4gZXhpc3RpbmcgcmVzdGF1cmFudCBhbmQgYSBjaXJjbGUgbGFiZWxlZCB3aXRoICZsc3F1bztBJnJzcXVvOyBvciAmbHNxdW87QiZyc3F1bzsgcmVwcmVzZW50cyB0aGUgbG9jYXRpb24gb2YgYW4gYXBhcnRtZW50LiBOb3RpY2UgdGhhdCBhIHJlc3RhdXJhbnQgaXMgYWxyZWFkeSBsb2NhdGVkIGF0IGVhY2ggYXBhcnRtZW50LiBFYWNoIHJvYWQganVuY3Rpb24gaXMgcmVwcmVzZW50ZWQgYnkgdGhlIGNvb3JkaW5hdGUgb2YgdGhlIG9yZGVyZWQgcGFpciBvZiBhIHZlcnRpY2FsIHJvYWQgYW5kIGEgaG9yaXpvbnRhbCByb2FkLiBUaGUgZGlzdGFuY2UgYmV0d2VlbiB0d28gbG9jYXRpb25zICh4MSwgeTEpIGFuZCAoeDIsIHkyKSBpcyBjb21wdXRlZCBhcyB8eDEteDJ8ICsgfHkxLXkyfC4gSW4gdGhlIGZpZ3VyZSBiZWxvdywgdGhlIGNvb3JkaW5hdGVzIG9mIEEgYW5kIEIgYXJlICgwLCA1KSBhbmQgKDEwLCA1KSwgcmVzcGVjdGl2ZWx5LiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2RtYXRscndqYS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMjdweDsgd2lkdGg6MjcycHhcIiBcLz48XC9wPlxyXG5cclxuPHA+TXIuIEtpbSBrbm93cyB0aGF0IHRoZSByZXNpZGVudHMgb2YgdGhlIHR3byBhcGFydG1lbnRzIGZyZXF1ZW50bHkgaGF2ZSBhIG1lZXRpbmcuIFNvLCBoZSB0aGlua3MgdGhhdCB0aGUgYmVzdCBsb2NhdGlvbiBvZiBhIG5ldyByZXN0YXVyYW50IGlzIGhhbGZ3YXkgYmV0d2VlbiB0d28gYXBhcnRtZW50cy4gQ29uc2lkZXJpbmcgbGVhc2UgZXhwZW5zZXMgYW5kIGV4aXN0aW5nIHJlc3RhdXJhbnRzLCBob3dldmVyLCBoZSBjYW4mcnNxdW87dCBzZWxlY3QgdGhlIG9wdGltYWwgbG9jYXRpb24gdW5jb25kaXRpb25hbGx5LiBIZW5jZSBoZSBkZWNpZGVzIHRvIHJlZ2FyZCBhIGxvY2F0aW9uIHNhdGlzZnlpbmcgdGhlIGZvbGxvd2luZyBjb25kaXRpb24gYXMgYSBnb29kIHBsYWNlLiBMZXQgZGlzdChwLCBxKSBiZSB0aGUgZGlzdGFuY2UgYmV0d2VlbiBwIGFuZCBxLiZuYnNwOzxcL3A+XHJcblxyXG48YmxvY2txdW90ZT5BIGxvY2F0aW9uIHAgaXMgYSBnb29kIHBsYWNlIGlmIGZvciBlYWNoIGV4aXN0aW5nIHJlc3RhdXJhbnQmcnNxdW87cyBsb2NhdGlvbiBxLCBkaXN0KHAsIEEpICZsdDsgZGlzdChxLCBBKSBvciBkaXN0KHAsIEIpICZsdDsgZGlzdChxLCBCKS4gSW4gb3RoZXIgd29yZHMsIHAgaXMgbm90IGEgZ29vZCBwbGFjZSBpZiB0aGVyZSBleGlzdHMgYW4gZXhpc3RpbmcgcmVzdGF1cmFudCZyc3F1bztzIGxvY2F0aW9uIHEgc3VjaCB0aGF0IGRpc3QocCwgQSkgJmdlOyBkaXN0KHEsIEEpIGFuZCBkaXN0KHAsIEIpICZnZTsgZGlzdChxLCBCKS4mbmJzcDs8XC9ibG9ja3F1b3RlPlxyXG5cclxuPHA+SW4gdGhlIGFib3ZlIGZpZ3VyZSwgdGhlIGxvY2F0aW9uICg3LCA0KSBpcyBhIGdvb2QgcGxhY2UuIEJ1dCB0aGUgbG9jYXRpb24gcCA9ICg0LCA2KSBpcyBub3QgZ29vZCBiZWNhdXNlIHRoZXJlIGlzIG5vIGFwYXJ0bWVudCB3aGljaCBpcyBjbG9zZXIgdG8gcCB0aGFuIHRoZSByZXN0YXVyYW50IGF0IHEgPSAoMywgNSksIGkuZS4sIGRpc3QocCwgQSkgPSA1ICZnZTsgZGlzdChxLCBBKSA9IDMgYW5kIGRpc3QocCwgQikgPSA3ICZnZTsgZGlzdChxLCBCKSA9IDcuIEFsc28sIHRoZSBsb2NhdGlvbiAoMCwgMCkgaXMgbm90IGdvb2QgZHVlIHRvIHRoZSByZXN0YXVyYW50IGF0ICgwLCA1KS4gTm90aWNlIHRoYXQgdGhlIGV4aXN0aW5nIHJlc3RhdXJhbnRzIGFyZSBwb3NpdGlvbmVkIHJlZ2FyZGxlc3Mgb2YgTXIuIEtpbSZyc3F1bztzIGNvbmRpdGlvbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+R2l2ZW4gbiBsb2NhdGlvbnMgb2YgZXhpc3RpbmcgcmVzdGF1cmFudHMsIHdyaXRlIGEgcHJvZ3JhbSB0byBjb21wdXRlIHRoZSBudW1iZXIgb2YgZ29vZCBwbGFjZXMgZm9yIGEgbmV3IHJlc3RhdXJhbnQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCB0aGUgaW5wdXQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IFQgY2FzZXMgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0d28gaW50ZWdlcnMgTSBhbmQgbiAoMiAmbGU7IE0gJmxlOyA2MCwwMDAgYW5kIDIgJmxlOyBuICZsZTsgNTAsMDAwKSwgd2hpY2ggcmVwcmVzZW50IHRoZSBzaXplIG9mIGEgY2l0eSBtYXAgYW5kIHRoZSBudW1iZXIgb2YgZXhpc3RpbmcgcmVzdGF1cmFudHMsIHJlc3BlY3RpdmVseS4gVGhlIChpKzEpLXRoIGxpbmUgb2YgYSB0ZXN0IGNhc2UgY29udGFpbnMgdHdvIGludGVnZXJzIHg8c3ViPmk8XC9zdWI+IGFuZCB5PHN1Yj5pPFwvc3ViPiAoaSA9IDEsIDIsIC4uLiAsIG4gYW5kIDAgJmxlOyB4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4gJmx0OyBNKSwgd2hpY2ggcmVwcmVzZW50cyB0aGUgY29vcmRpbmF0ZSBvZiB0aGUgaS10aCBleGlzdGluZyByZXN0YXVyYW50LiBBc3N1bWUgdGhhdCBhbGwgcmVzdGF1cmFudHMgaGF2ZSBkaXN0aW5jdCBjb29yZGluYXRlcyBhbmQgdGhhdCB0aGUgdHdvIGFwYXJ0bWVudHMgQSBhbmQgQiBhcmUgcG9zaXRpb25lZCBhdCB0aGUgbG9jYXRpb25zIG9mIDEtc3QgcmVzdGF1cmFudCBhbmQgMi1uZCByZXN0YXVyYW50LiBOb3RpY2UgdGhhdCBBIGFuZCBCIGFyZSBwbGFjZWQgb24gdGhlIHNhbWUgaG9yaXpvbnRhbCBsaW5lLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBQcmludCB0aGUgbnVtYmVyIG9mIGdvb2QgcGxhY2VzIHdoaWNoIGNhbiBiZSBmb3VuZCBpbiBhIGdpdmVuIGNpdHkgbWFwLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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