시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB56111032.258%

문제

선영: "상근이가 총을 먼저 쐈어요!"

상덕: "아니에요. 희원이가 있는 쪽에서 총소리가 먼저 났어요!"

논쟁은 얼마 전에 있었던 큰 총격전에 대한 재판내내 계속 되었다. 다행히도 총격전에 참가한 모든 사람은 죽지 않았다. 하지만, 총이 발사된 순서는 모두가 동의하지 않았다. 모든 사람은 최대 한 발을 발사했다. 하지만, 모든 일이 너무나 빠르게 일어났다. 총이 발사된 순서를 알아내야 유죄와 무죄를 판결할 수 있기 때문에, 순서를 알아내는 것은 매우 중요하다.

갑자기 경찰관 현우가 논쟁에 끼어들었다.

현우: "난 총격전이 일어난 그 시점의 위성 사진을 가지고 있다. 너희들이 어디에 있는 지를 정확하게 알 수 있지. 상덕이는 상근이보다 희원이에게 매우 가깝게 있었고, 선영이는 상근이보다 희원이에게 조금 가깝게 있었군. 소리는 1초에 340m를 움직이지. 상덕이는 상근이가 총을 먼저 쐈다고 하더라도, 희원이의 총소리를 먼저 들었을 거야. 그런데, 선영이는 희원이에게 조금 가깝게 있었는데도 상근이의 총소리를 먼저 들었네? 상근이가 제일 처음으로 총을 발사한 사람이네!"

위와 같은 상황이 주어졌을 때, 총을 발사한 순서를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개이다.

테스트 케이스의 첫째 줄에는 총격전에 연루된 사람의 수 n (2 ≤ n ≤ 100)과 진술의 수 m (1 ≤ m ≤ 1000) 이 주어진다.

다음 n개 줄에는 사람의 이름 S와 그 사람의 위치 x와 y가 주어진다. 이름은 길이가 최대 20이며, 알파벳 소문자와 대문자로만 이루어져 있다. 좌표는 원점으로부터 떨어진 거리이며 단위는 미터이다.

다음 m개 줄에는 각 사람의 진술 "S1 heard S2 firing before S3"가 주어진다. S1, S2, S3은 사람의 이름이며, S2 ≠ S3이다.

만약, 어떤 사람이 S2, S3로 언급된 적이 없으면, 그 사람은 총을 쏘지 않았다고 가정한다. 두 사람이 같은 장소에 있는 경우는 없다.

테스트 케이스는 정답에 영향을 주지 않기 위해 거리의 오차가 10-7보다 작게 만들어져 있다.

출력

각 테스트 케이스 마다 총을 쏜 순서를 출력한다. 만약, 가능한 순서가 여러 가지라면 "UNKNOWN"을 출력하고, 가능한 순서가 없는 경우에는 "IMPOSSIBLE"을 출력한다.

예제 입력 1

3
4 2
BillyTheKid 0 0
Andy 10 0
John 19 0
Larry 20 0
Andy heard BillyTheKid firing before John
Larry heard John firing before BillyTheKid
2 2
Andy 0 0
Beate 0 1
Andy heard Beate firing before Andy
Beate heard Andy firing before Beate
3 1
Andy 0 0
Beate 0 1
Charles 1 3
Beate heard Andy firing before Charles

예제 출력 1

BillyTheKid John
IMPOSSIBLE
UNKNOWN
W3sicHJvYmxlbV9pZCI6IjM2NTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkMWRcdWFjYTlcdWM4MDQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzEyMFx1YzYwMTogJnF1b3Q7XHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1Y2QxZFx1Yzc0NCBcdWJhM2NcdWM4MDAgXHVjNDA4XHVjNWI0XHVjNjk0ISZxdW90OzxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWIzNTU6ICZxdW90O1x1YzU0NFx1YjJjOFx1YzVkMFx1YzY5NC4gXHVkNzZjXHVjNmQwXHVjNzc0XHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWNhYmRcdWM1ZDBcdWMxMWMgXHVjZDFkXHVjMThjXHViOWFjXHVhYzAwIFx1YmEzY1x1YzgwMCBcdWIwYWNcdWM1YjRcdWM2OTQhJnF1b3Q7PFwvcD5cclxuXHJcbjxwPlx1YjE3Y1x1YzdjMVx1Yzc0MCBcdWM1YmNcdWI5YzggXHVjODA0XHVjNWQwIFx1Yzc4OFx1YzVjOFx1YjM1OCBcdWQwNzAgXHVjZDFkXHVhY2E5XHVjODA0XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM3YWNcdWQzMTBcdWIwYjRcdWIwYjQgXHVhY2M0XHVjMThkIFx1YjQxOFx1YzVjOFx1YjJlNC4gXHViMmU0XHVkNTg5XHVkNzg4XHViM2M0IFx1Y2QxZFx1YWNhOVx1YzgwNFx1YzVkMCBcdWNjMzhcdWFjMDBcdWQ1NWMgXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWM4ZmRcdWM5YzAgXHVjNTRhXHVjNTU4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1Y2QxZFx1Yzc3NCBcdWJjMWNcdWMwYWNcdWI0MWMgXHVjMjFjXHVjMTFjXHViMjk0IFx1YmFhOFx1YjQ1MFx1YWMwMCBcdWIzZDlcdWM3NThcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNTU4XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjMGFjXHViNzhjXHVjNzQwIFx1Y2Q1Y1x1YjMwMCBcdWQ1NWMgXHViYzFjXHVjNzQ0IFx1YmMxY1x1YzBhY1x1ZDU4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWJhYThcdWI0ZTAgXHVjNzdjXHVjNzc0IFx1YjEwOFx1YmIzNFx1YjA5OCBcdWJlNjBcdWI5NzRcdWFjOGMgXHVjNzdjXHVjNWI0XHViMGFjXHViMmU0LiBcdWNkMWRcdWM3NzQgXHViYzFjXHVjMGFjXHViNDFjIFx1YzIxY1x1YzExY1x1Yjk3YyBcdWM1NGNcdWM1NDRcdWIwYjRcdWM1N2MgXHVjNzIwXHVjOGM0XHVjNjQwIFx1YmIzNFx1YzhjNFx1Yjk3YyBcdWQzMTBcdWFjYjBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzIxY1x1YzExY1x1Yjk3YyBcdWM1NGNcdWM1NDRcdWIwYjRcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YjllNFx1YzZiMCBcdWM5MTFcdWM2OTRcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMxMVx1Yzc5MFx1YWUzMCBcdWFjYmRcdWNjMzBcdWFkMDAgXHVkNjA0XHVjNmIwXHVhYzAwIFx1YjE3Y1x1YzdjMVx1YzVkMCBcdWIwN2NcdWM1YjRcdWI0ZTRcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDYwNFx1YzZiMDogJnF1b3Q7XHViMDljIFx1Y2QxZFx1YWNhOVx1YzgwNFx1Yzc3NCBcdWM3N2NcdWM1YjRcdWIwOWMgXHVhZGY4IFx1YzJkY1x1YzgxMFx1Yzc1OCBcdWM3MDRcdWMxMzEgXHVjMGFjXHVjOWM0XHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YjEwOFx1ZDc2Y1x1YjRlNFx1Yzc3NCBcdWM1YjRcdWI1MTRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzljMFx1Yjk3YyBcdWM4MTVcdWQ2NTVcdWQ1NThcdWFjOGMgXHVjNTRjIFx1YzIxOCBcdWM3ODhcdWM5YzAuIFx1YzBjMVx1YjM1NVx1Yzc3NFx1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWJjZjRcdWIyZTQgXHVkNzZjXHVjNmQwXHVjNzc0XHVjNWQwXHVhYzhjIFx1YjllNFx1YzZiMCBcdWFjMDBcdWFlNWRcdWFjOGMgXHVjNzg4XHVjNWM4XHVhY2UwLCBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHViY2Y0XHViMmU0IFx1ZDc2Y1x1YzZkMFx1Yzc3NFx1YzVkMFx1YWM4YyBcdWM4NzBcdWFlMDggXHVhYzAwXHVhZTVkXHVhYzhjIFx1Yzc4OFx1YzVjOFx1YWQ3MC4gXHVjMThjXHViOWFjXHViMjk0IDFcdWNkMDhcdWM1ZDAgMzQwbVx1Yjk3YyBcdWM2YzBcdWM5YzFcdWM3NzRcdWM5YzAuIFx1YzBjMVx1YjM1NVx1Yzc3NFx1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjZDFkXHVjNzQ0IFx1YmEzY1x1YzgwMCBcdWM0MDhcdWIyZTRcdWFjZTAgXHVkNTU4XHViMzU0XHViNzdjXHViM2M0LCBcdWQ3NmNcdWM2ZDBcdWM3NzRcdWM3NTggXHVjZDFkXHVjMThjXHViOWFjXHViOTdjIFx1YmEzY1x1YzgwMCBcdWI0ZTRcdWM1YzhcdWM3NDQgXHVhYzcwXHVjNTdjLiBcdWFkZjhcdWI3ZjBcdWIzNzAsIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWQ3NmNcdWM2ZDBcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjODcwXHVhZTA4IFx1YWMwMFx1YWU1ZFx1YWM4YyBcdWM3ODhcdWM1YzhcdWIyOTRcdWIzNzBcdWIzYzQmbmJzcDtcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjZDFkXHVjMThjXHViOWFjXHViOTdjIFx1YmEzY1x1YzgwMCBcdWI0ZTRcdWM1YzhcdWIxMjQ/IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM4MWNcdWM3N2MgXHVjYzk4XHVjNzRjXHVjNzNjXHViODVjIFx1Y2QxZFx1Yzc0NCBcdWJjMWNcdWMwYWNcdWQ1NWMgXHVjMGFjXHViNzhjXHVjNzc0XHViMTI0ISZxdW90OzxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YzBjMVx1ZDY2OVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWNkMWRcdWM3NDQgXHViYzFjXHVjMGFjXHVkNTVjIFx1YzIxY1x1YzExY1x1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWNkNWNcdWIzMDAgMTAwXHVhYzFjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjZDFkXHVhY2E5XHVjODA0XHVjNWQwIFx1YzVmMFx1YjhlOFx1YjQxYyBcdWMwYWNcdWI3OGNcdWM3NTggXHVjMjE4IG4gKDIgJmxlOyBuICZsZTsgMTAwKVx1YWNmYyBcdWM5YzRcdWMyMjBcdWM3NTggXHVjMjE4IG0gKDEgJmxlOyBtICZsZTsgMTAwMCkgXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIG5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWM3NzRcdWI5ODQgU1x1YzY0MCBcdWFkZjggXHVjMGFjXHViNzhjXHVjNzU4IFx1YzcwNFx1Y2U1OCB4XHVjNjQwIHlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI5ODRcdWM3NDAgXHVhZTM4XHVjNzc0XHVhYzAwIFx1Y2Q1Y1x1YjMwMCAyMFx1Yzc3NFx1YmE3MCwgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1YzY0MCBcdWIzMDBcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjODhjXHVkNDVjXHViMjk0IFx1YzZkMFx1YzgxMFx1YzczY1x1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWI1YThcdWM1YjRcdWM5YzQgXHVhYzcwXHViOWFjXHVjNzc0XHViYTcwIFx1YjJlOFx1YzcwNFx1YjI5NCBcdWJiZjhcdWQxMzBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBtXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzljNFx1YzIyMCAmcXVvdDtTMSBoZWFyZCBTMiBmaXJpbmcgYmVmb3JlIFMzJnF1b3Q7XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gUzEsIFMyLCBTM1x1Yzc0MCBcdWMwYWNcdWI3OGNcdWM3NTggXHVjNzc0XHViOTg0XHVjNzc0XHViYTcwLCBTMiAmbmU7IFMzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QsIFx1YzViNFx1YjVhNCBcdWMwYWNcdWI3OGNcdWM3NzQgUzIsIFMzXHViODVjIFx1YzViOFx1YWUwOVx1YjQxYyBcdWM4MDFcdWM3NzQgXHVjNWM2XHVjNzNjXHViYTc0LCBcdWFkZjggXHVjMGFjXHViNzhjXHVjNzQwIFx1Y2QxZFx1Yzc0NCBcdWMzZDhcdWM5YzAgXHVjNTRhXHVjNTU4XHViMmU0XHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU1Y1x1YjJlNC4gXHViNDUwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWFjMTlcdWM3NDAgXHVjN2E1XHVjMThjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YzgxNVx1YjJmNVx1YzVkMCBcdWM2MDFcdWQ1YTVcdWM3NDQgXHVjOGZjXHVjOWMwIFx1YzU0YVx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVhYzcwXHViOWFjXHVjNzU4IFx1YzYyNFx1Y2MyOFx1YWMwMCAxMDxzdXA+LTc8XC9zdXA+XHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM4YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YjljOFx1YjJlNCBcdWNkMWRcdWM3NDQgXHVjM2RjIFx1YzIxY1x1YzExY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVhYzAwXHViMmE1XHVkNTVjIFx1YzIxY1x1YzExY1x1YWMwMCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHViNzdjXHViYTc0ICZxdW90O1VOS05PV04mcXVvdDtcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjMjFjXHVjMTFjXHVhYzAwIFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJnF1b3Q7SU1QT1NTSUJMRSZxdW90O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzY1NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNtb2tpbmcgZ3VuIiwiZGVzY3JpcHRpb24iOiI8cD5BbmR5OiAmcmRxdW87QmlsbHkgdGhlIEtpZCBcdWZiMDFyZWQgXHVmYjAxcnN0ISZyZHF1bzs8XC9wPlxyXG5cclxuPHA+TGFycnk6ICZyZHF1bztObywgSSZyc3F1bzttIHN1cmUgSSBoZWFyZCB0aGUgXHVmYjAxcnN0IHNob3QgY29taW5nIGZyb20gSm9obiEmcmRxdW87PFwvcD5cclxuXHJcbjxwPlRoZSBhcmd1bWVudHMgd2VudCBiYWNrIGFuZCBmb3J0aCBkdXJpbmcgdGhlIHRyaWFsIGFmdGVyIHRoZSBiaWcgc2hvb3QtZG93biwgc29tZXdoZXJlIGluIHRoZSBvbGQgd2lsZCB3ZXN0LiBNaXJhY3Vsb3VzbHksIGV2ZXJ5Ym9keSBoYWQgc3Vydml2ZWQgKGFsdGhvdWdoIHRoZXJlIHdlcmUgc2VyaW91cyBpbmp1cmllcyksIGJ1dCBub2JvZHkgY291bGQgYWdyZWUgYWJvdXQgdGhlIGV4YWN0IHNlcXVlbmNlIG9mIHNob3RzIHRoYXQgaGFkIGJlZW4gXHVmYjAxcmVkLiBJdCB3YXMga25vd24gdGhhdCBldmVyeWJvZHkgaGFkIFx1ZmIwMXJlZCBhdCBtb3N0IG9uZSBzaG90LCBidXQgZXZlcnl0aGluZyBoYWQgaGFwcGVuZWQgdmVyeSBmYXN0LiBEZXRlcm1pbmluZyB0aGUgcHJlY2lzZSBvcmRlciBvZiB0aGUgc2hvdHMgd2FzIGltcG9ydGFudCBmb3IgYXNzaWduaW5nIGd1aWx0IGFuZCBwZW5hbHRpZXMuPFwvcD5cclxuXHJcbjxwPkJ1dCB0aGVuIHRoZSBzaGVyaWZmLCBXaWxseSB0aGUgV2lzZSwgaW50ZXJydXB0ZWQ6ICZyZHF1bztMb29rLCBJJnJzcXVvO3ZlIGdvdCBhIHNhdGVsbGl0ZSBpbWFnZSBmcm9tIHRoZSB0aW1lIG9mIHRoZSBzaG9vdGluZywgc2hvd2luZyBleGFjdGx5IHdoZXJlIGV2ZXJ5Ym9keSB3YXMgbG9jYXRlZC4gQXMgaXQgdHVybnMgb3V0LCBMYXJyeSB3YXMgbG9jYXRlZCBtdWNoIGNsb3NlciB0byBKb2huIHRoYW4gdG8gQmlsbHkgdGhlIEtpZCwgd2hpbGUgQW5keSB3YXMgbG9jYXRlZCBqdXN0IHNsaWdodGx5IGNsb3NlciB0byBKb2huIHRoYW4gdG8gQmlsbHkgdGhlIEtpZC4gVGh1cywgYmVjYXVzZSBzb3VuZCB0cmF2ZWxzIHdpdGggYSBcdWZiMDFuaXRlIHNwZWVkIG9mIDM0MCBtZXRlcnMgcGVyIHNlY29uZCwgTGFycnkgbWF5IGhhdmUgaGVhcmQgSm9obiZyc3F1bztzIHNob3QgXHVmYjAxcnN0LCBldmVuIGlmIEJpbGx5IHRoZSBLaWQgXHVmYjAxcmVkIFx1ZmIwMXJzdC4gQnV0LCBhbHRob3VnaCBBbmR5IHdhcyBjbG9zZXIgdG8gSm9obiB0aGFuIHRvIEJpbGx5IHRoZSBLaWQsIGhlIGhlYXJkIEJpbGx5IHRoZSBLaWQmcnNxdW87cyBzaG90IFx1ZmIwMXJzdCAmbmRhc2g7IHNvIHdlIGtub3cgZm9yIGEgZmFjdCB0aGF0IEJpbGx5IHRoZSBLaWQgd2FzIHRoZSBvbmUgd2hvIFx1ZmIwMXJlZCBcdWZiMDFyc3QhPFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byB3cml0ZSBhIHByb2dyYW0gdG8gZGVkdWNlIHRoZSBleGFjdCBzZXF1ZW5jZSBvZiBzaG90cyBcdWZiMDFyZWQgaW4gc2l0dWF0aW9ucyBsaWtlIHRoZSBhYm92ZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBcdWZiMDFyc3QgbGluZSBhIHBvc2l0aXZlIGludGVnZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIHR3byBpbnRlZ2VycyBuICgyICZsZTsgbiAmbGU7IDEwMCkgYW5kIG0gKDEgJmxlOyBtICZsZTsgMSAwMDApOiB0aGUgbnVtYmVyIG9mIHBlb3BsZSBpbnZvbHZlZCBhbmQgdGhlIG51bWJlciBvZiBvYnNlcnZhdGlvbnMuPFwvbGk+XHJcblx0PGxpPm4gbGluZXMgd2l0aCBhIHN0cmluZyBTLCBjb25zaXN0aW5nIG9mIHVwIHRvIDIwIGxvd2VyIGFuZCB1cHBlciBjYXNlIGxldHRlcnMsIGFuZCB0d28gaW50ZWdlcnMgeCBhbmQgeSAoMCAmbGU7IHgsIHkgJmxlOyAxIDAwMCAwMDApOiB0aGUgdW5pcXVlIGlkZW50aVx1ZmIwMWVyIGZvciBhIHBlcnNvbiBhbmQgaGlzXC9oZXIgcG9zaXRpb24gaW4gQ2FydGVzaWFuIGNvb3JkaW5hdGVzLCBpbiBtZXRyZXMgZnJvbSB0aGUgb3JpZ2luLjxcL2xpPlxyXG5cdDxsaT5tIGxpbmVzIG9mIHRoZSBmb3JtICZsZHF1bztTMSBoZWFyZCBTMiBmaXJpbmcgYmVmb3JlIFMzJnJkcXVvOywgd2hlcmUgUzEsIFMyIGFuZCBTMyBhcmUgaWRlbnRpXHVmYjAxZXJzIGFtb25nIHRoZSBwZW9wbGUgaW52b2x2ZWQsIGFuZCBTMiAmbmU7IFMzLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPklmIGEgcGVyc29uIHdhcyBuZXZlciBtZW50aW9uZWQgYXMgUzIgb3IgUzMsIHRoZW4gaXQgY2FuIGJlIGFzc3VtZWQgdGhhdCB0aGlzIHBlcnNvbiBuZXZlciBcdWZiMDFyZWQsIGFuZCBvbmx5IGFjdGVkIGFzIGEgd2l0bmVzcy4gTm8gdHdvIHBlcnNvbnMgYXJlIGxvY2F0ZWQgaW4gdGhlIHNhbWUgcG9zaXRpb24uPFwvcD5cclxuXHJcbjxwPlRoZSB0ZXN0IGNhc2VzIGFyZSBjb25zdHJ1Y3RlZCBzbyB0aGF0IGFuIGVycm9yIG9mIGxlc3MgdGhhbiAxMDxzdXA+LTc8XC9zdXA+IGluIG9uZSBkaXN0YW5jZSBjYWxjdWxhdGlvbiB3aWxsIG5vdCBhZmZlY3QgdGhlIG91dHB1dC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggdGhlIG9yZGVyaW5nIG9mIHRoZSBzaG9vdGVycyB0aGF0IGlzIGNvbXBhdGlibGUgd2l0aCBhbGwgb2YgdGhlIG9ic2VydmF0aW9ucywgZm9ybWF0dGVkIGFzIHRoZSBpZGVudGlcdWZiMDFlcnMgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SWYgbXVsdGlwbGUgZGlzdGluY3Qgb3JkZXJpbmdzIGFyZSBwb3NzaWJsZSwgb3V0cHV0ICZsZHF1bztVTktOT1dOJnJkcXVvOyBpbnN0ZWFkLiBJZiBubyBvcmRlcmluZyBpcyBjb21wYXRpYmxlIHdpdGggdGhlIG9ic2VydmF0aW9ucywgb3V0cHV0ICZsZHF1bztJTVBPU1NJQkxFJnJkcXVvOyBpbnN0ZWFkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2011 G번