시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 313 30 25 15.924%

문제

최근에 유능한 학생 홍준이는 일반적인 무방향성 그래프에서는 어려운 문제 몇 개가 홀수 싸이클이 없을 경우 다항 시간안에 해결되는 것을 알게 되었다. 방향성 그래프에서 같은지도 확인하기 위해 그의 지도교수 백준과 함께 관련 연구를 하기로 했다. 연구의 첫 목표는 방향성 그래프에서 홀수 싸이클이 있는지 확인하는 것이다. 홍준이가 찾은 알고리즘은 연구실에서 성능이 좋기로 인정을 받지만, 더욱 더 효율 좋은 알고리즘을 찾고 싶어한다. 그를 도와 아주 아주 성능좋은 방향성 그래프에서 홀수 싸이클을 찾는 알고리즘을 찾자. 홀수 싸이클이 존재한다면 존재 유무 뿐만아니라 싸이클이 "어떤" 싸이클이 존재하는지도 찾아내자.

G를 자기 루프와 중복 간선 없는 단순 방향성 그래프라고 하자. 어떤 두 정점 v, w가 G에 있다고 할 때, v에서 w로 가는 경로를 (u1, u2, … ,ul)라 하자. 이때, ui들은 서로 다르고, u1 = v, ul = w이고, 1이상 l 미만인 모든 i에 대해 ui에서 ui+1로 가는 방향성 간선이 존재한다. 만약 l ≥ 2이고 ul에서 u1으로 가는 방향성 간선이 존재한다면, 이를 싸이클이라고 한다. 홀수 싸이클이란 싸이클 중에서 길이 l이 홀수인 싸이클을 의미한다. 아래 <그림 1>을 참고하자.


<그림 1> 단순 방향성 그래프들

입력

입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 입력으로 주어진다. 이어서 각 테스트케이스마다 첫 줄에는 정점의 개수를 나타내는 자연수 N과 간선의 수를 나타내는 자연수 M이 주어진다. 정점의 번호는 1부터 N까지 매겨져있고, N ≤ 100,000, M ≤ 1,000,000이다. 이후 M개의 줄에는 단순 방향성 그래프의 간선들이 주어진다. 만약 v w가 주어졌다면 v번 정점에서 w번 정점으로 가는 방향성 간선이 있다는 뜻이다.

출력

각 테스트케이스에 대해서 홀수 싸이클이 없으면 -1을 출력하고, 있다면 1을 출력한 뒤 싸이클의 크기, 싸이클에 있는 정점 번호들을 방문 순서대로 줄로 구분하여 출력한다. 싸이클에 있는 정점 번호들이 서로 달라야 됨에 유의하자.

예제 입력 1

4
3 3
2 3
2 1
1 3
3 4
2 3
3 2
1 2
1 3
3 4
2 1
2 3
1 3
3 2
8 9
1 2
2 3
3 4
4 1
5 6
6 7
7 8
8 5
5 8

예제 출력 1

-1
-1
1
3
2
1
3
-1
W3sicHJvYmxlbV9pZCI6IjExNDk4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNjQwXHVjMjE4IFx1YzJmOFx1Yzc3NFx1ZDA3NCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjZDVjXHVhZGZjXHVjNWQwIFx1YzcyMFx1YjJhNVx1ZDU1YyBcdWQ1NTlcdWMwZGQgXHVkNjRkXHVjOTAwXHVjNzc0XHViMjk0IFx1Yzc3Y1x1YmMxOFx1YzgwMVx1Yzc3OCBcdWJiMzRcdWJjMjlcdWQ1YTVcdWMxMzEgXHVhZGY4XHViNzk4XHVkNTA0XHVjNWQwXHVjMTFjXHViMjk0IFx1YzViNFx1YjgyNFx1YzZiNCBcdWJiMzhcdWM4MWMgXHViYTg3IFx1YWMxY1x1YWMwMCBcdWQ2NDBcdWMyMTggXHVjMmY4XHVjNzc0XHVkMDc0XHVjNzc0IFx1YzVjNlx1Yzc0NCBcdWFjYmRcdWM2YjAgXHViMmU0XHVkNTZkIFx1YzJkY1x1YWMwNFx1YzU0OFx1YzVkMCBcdWQ1NzRcdWFjYjBcdWI0MThcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YzU0Y1x1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuIFx1YmMyOVx1ZDVhNVx1YzEzMSBcdWFkZjhcdWI3OThcdWQ1MDRcdWM1ZDBcdWMxMWMgXHVhYzE5XHVjNzQwXHVjOWMwXHViM2M0IFx1ZDY1NVx1Yzc3OFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVhZGY4XHVjNzU4IFx1YzljMFx1YjNjNFx1YWQ1MFx1YzIxOCBcdWJjMzFcdWM5MDBcdWFjZmMgXHVkNTY4XHVhZWQ4IFx1YWQwMFx1YjgyOCBcdWM1ZjBcdWFkNmNcdWI5N2MgXHVkNTU4XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC4gXHVjNWYwXHVhZDZjXHVjNzU4IFx1Y2NhYiBcdWJhYTlcdWQ0NWNcdWIyOTQgXHViYzI5XHVkNWE1XHVjMTMxIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YzVkMFx1YzExYyBcdWQ2NDBcdWMyMTggXHVjMmY4XHVjNzc0XHVkMDc0XHVjNzc0IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWQ2NTVcdWM3NzhcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWQ2NGRcdWM5MDBcdWM3NzRcdWFjMDAgXHVjYzNlXHVjNzQwIFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1Yzc0MCBcdWM1ZjBcdWFkNmNcdWMyZTRcdWM1ZDBcdWMxMWMgXHVjMTMxXHViMmE1XHVjNzc0IFx1Yzg4Ylx1YWUzMFx1Yjg1YyBcdWM3NzhcdWM4MTVcdWM3NDQgXHViYzFiXHVjOWMwXHViOWNjLCBcdWIzNTRcdWM2YjEgXHViMzU0IFx1ZDZhOFx1YzcyOCBcdWM4OGJcdWM3NDAgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQ0IFx1Y2MzZVx1YWNlMCBcdWMyZjZcdWM1YjRcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1Yjk3YyBcdWIzYzRcdWM2NDAgXHVjNTQ0XHVjOGZjIFx1YzU0NFx1YzhmYyBcdWMxMzFcdWIyYTVcdWM4OGJcdWM3NDAgXHViYzI5XHVkNWE1XHVjMTMxIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YzVkMFx1YzExYyBcdWQ2NDBcdWMyMTggXHVjMmY4XHVjNzc0XHVkMDc0XHVjNzQ0IFx1Y2MzZVx1YjI5NCBcdWM1NGNcdWFjZTBcdWI5YWNcdWM5OThcdWM3NDQgXHVjYzNlXHVjNzkwLiBcdWQ2NDBcdWMyMTggXHVjMmY4XHVjNzc0XHVkMDc0XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNFx1YmE3NCBcdWM4NzRcdWM3YWMgXHVjNzIwXHViYjM0IFx1YmZkMFx1YjljY1x1YzU0NFx1YjJjOFx1Yjc3YyBcdWMyZjhcdWM3NzRcdWQwNzRcdWM3NzQgJnF1b3Q7XHVjNWI0XHViNWE0JnF1b3Q7IFx1YzJmOFx1Yzc3NFx1ZDA3NFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTRcdWM5YzBcdWIzYzQgXHVjYzNlXHVjNTQ0XHViMGI0XHVjNzkwLjxcL3A+XHJcblxyXG48cD5HXHViOTdjIFx1Yzc5MFx1YWUzMCBcdWI4ZThcdWQ1MDRcdWM2NDAgXHVjOTExXHViY2Y1IFx1YWMwNFx1YzEyMCBcdWM1YzZcdWIyOTQgXHViMmU4XHVjMjFjIFx1YmMyOVx1ZDVhNVx1YzEzMSBcdWFkZjhcdWI3OThcdWQ1MDRcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWM1YjRcdWI1YTQgXHViNDUwIFx1YzgxNVx1YzgxMCB2LCB3XHVhYzAwIEdcdWM1ZDAgXHVjNzg4XHViMmU0XHVhY2UwIFx1ZDU2MCBcdWI1NGMsIHZcdWM1ZDBcdWMxMWMgd1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHVhY2JkXHViODVjXHViOTdjICh1PHN1Yj4xPFwvc3ViPiwgdTxzdWI+MjxcL3N1Yj4sICZoZWxsaXA7ICx1PHN1Yj5sPFwvc3ViPilcdWI3N2MgXHVkNTU4XHVjNzkwLiBcdWM3NzRcdWI1NGMsIHU8c3ViPmk8XC9zdWI+XHViNGU0XHVjNzQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzRcdWFjZTAsIHU8c3ViPjE8XC9zdWI+ID0gdiwgdTxzdWI+bDxcL3N1Yj4gPSB3XHVjNzc0XHVhY2UwLCAxXHVjNzc0XHVjMGMxIGwgXHViYmY4XHViOWNjXHVjNzc4IFx1YmFhOFx1YjRlMCBpXHVjNWQwIFx1YjMwMFx1ZDU3NCB1PHN1Yj5pPFwvc3ViPlx1YzVkMFx1YzExYyB1PHN1Yj5pKzE8XC9zdWI+XHViODVjIFx1YWMwMFx1YjI5NCBcdWJjMjlcdWQ1YTVcdWMxMzEgXHVhYzA0XHVjMTIwXHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIGwgJmdlOyAyXHVjNzc0XHVhY2UwIHU8c3ViPmw8XC9zdWI+XHVjNWQwXHVjMTFjIHU8c3ViPjE8XC9zdWI+XHVjNzNjXHViODVjIFx1YWMwMFx1YjI5NCBcdWJjMjlcdWQ1YTVcdWMxMzEgXHVhYzA0XHVjMTIwXHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNFx1YmE3NCwgXHVjNzc0XHViOTdjIFx1YzJmOFx1Yzc3NFx1ZDA3NFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1ZDY0MFx1YzIxOCBcdWMyZjhcdWM3NzRcdWQwNzRcdWM3NzRcdWI3ODAgXHVjMmY4XHVjNzc0XHVkMDc0IFx1YzkxMVx1YzVkMFx1YzExYyBcdWFlMzhcdWM3NzQgbFx1Yzc3NCBcdWQ2NDBcdWMyMThcdWM3NzggXHVjMmY4XHVjNzc0XHVkMDc0XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHVjNTQ0XHViNzk4ICZsdDtcdWFkZjhcdWI5YmMgMSZndDtcdWM3NDQgXHVjYzM4XHVhY2UwXHVkNTU4XHVjNzkwLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMTE0OThcLzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTIycHg7IHdpZHRoOjU0M3B4XCIgXC8+PGJyIFwvPlxyXG4mbHQ7XHVhZGY4XHViOWJjIDEmZ3Q7IFx1YjJlOFx1YzIxYyBcdWJjMjlcdWQ1YTVcdWMxMzEgXHVhZGY4XHViNzk4XHVkNTA0XHViNGU0PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTQgXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM3OTBcdWM1ZjBcdWMyMTggVFx1YWMwMCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWM1YjRcdWMxMWMgXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1Yzc5MFx1YzVmMFx1YzIxOCBOXHVhY2ZjIFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1Yzc5MFx1YzVmMFx1YzIxOCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjODE1XHVjODEwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCAxXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzAgXHViOWU0XHVhY2E4XHVjODM4XHVjNzg4XHVhY2UwLCBOICZsZTsgMTAwLDAwMCwgTSAmbGU7IDEsMDAwLDAwMFx1Yzc3NFx1YjJlNC4gXHVjNzc0XHVkNmM0IE1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjJlOFx1YzIxYyBcdWJjMjlcdWQ1YTVcdWMxMzEgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1YWMwNFx1YzEyMFx1YjRlNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjljY1x1YzU3ZCB2IHdcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHViMmU0XHViYTc0IHZcdWJjODggXHVjODE1XHVjODEwXHVjNWQwXHVjMTFjIHdcdWJjODggXHVjODE1XHVjODEwXHVjNzNjXHViODVjIFx1YWMwMFx1YjI5NCBcdWJjMjlcdWQ1YTVcdWMxMzEgXHVhYzA0XHVjMTIwXHVjNzc0IFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVkNjQwXHVjMjE4IFx1YzJmOFx1Yzc3NFx1ZDA3NFx1Yzc3NCBcdWM1YzZcdWM3M2NcdWJhNzQgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBcdWM3ODhcdWIyZTRcdWJhNzQgMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWMgXHViNGE0IFx1YzJmOFx1Yzc3NFx1ZDA3NFx1Yzc1OCBcdWQwNmNcdWFlMzAsIFx1YzJmOFx1Yzc3NFx1ZDA3NFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjODE1XHVjODEwIFx1YmM4OFx1ZDYzOFx1YjRlNFx1Yzc0NCBcdWJjMjlcdWJiMzggXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzkwNFx1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWMyZjhcdWM3NzRcdWQwNzRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzgxNVx1YzgxMCBcdWJjODhcdWQ2MzhcdWI0ZTRcdWM3NzQgXHVjMTFjXHViODVjIFx1YjJlY1x1Yjc3Y1x1YzU3YyBcdWI0MjhcdWM1ZDAgXHVjNzIwXHVjNzU4XHVkNTU4XHVjNzkwLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExNDk4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiT2RkIEN5Y2xlIiwiZGVzY3JpcHRpb24iOiI8cD5SZWNlbnRseSwgYSBzbWFydCBzdHVkZW50IFNlb0ppbiByZWFsaXplZCB0aGF0IG5vdCBhIGZldyBoYXJkIHByb2JsZW1zIGZvciBnZW5lcmFsIHVuZGlyZWN0ZWQgZ3JhcGhzIGFyZSBwb2x5bm9taWFsbHkgc29sdmFibGUgZm9yIGdyYXBocyB0aGF0IGhhdmUgbm8gY3ljbGVzIG9mIG9kZCBsZW5ndGguIFdvbmRlcmluZyB3aGV0aGVyIG9yIG5vdCB0aGUgc2FtZSBmb2xsb3dzIGZvciBkaXJlY3RlZCBncmFwaHMsIHNoZSBtYWRlIHVwIGhlciBtaW5kIHRvIHN0YXJ0IGEgc3R1ZHkgb24gdGhlIHN1YmplY3QgdW5kZXIgdGhlIHN1cGVydmlzaW9uIG9mIEh5ZW9uZ1Nlb2ssIGEgZGlzdGluZ3Vpc2hlZCBzY2hvbGFyIGluIHRoaXMgZmllbGQuIEhlciBmaXJzdCByZXNlYXJjaCBmaW5kaW5nIGlzIGVmZmVjdGl2ZSByZWNvZ25pdGlvbiBvZiB0aGUgZGlyZWN0ZWQgZ3JhcGhzIHdpdGhvdXQgb2RkIGN5Y2xlcywgaS5lLiwgYW4gYWxnb3JpdGhtIGZvciBkZXRlcm1pbmluZyBpZiBhIGdpdmVuIGRpcmVjdGVkIGdyYXBoIGhhcyBhIGN5Y2xlIG9mIG9kZCBsZW5ndGguIFN0aWxsLCBzaGUgaXMgcHJvbW90aW5nIHV0bW9zdCBlZmZpY2llbmN5IGluIHJlY29nbml6aW5nIGhlciBjbGFzcyBvZiBncmFwaHMuIEluIG9yZGVyIHRvIGhlbHAgaGVyLCB5b3UgYXJlIGdvaW5nIHRvIHdyaXRlIGFuIHVsdHJhLWVmZmljaWVudCBwcm9ncmFtIHRoYXQgZGV0ZXJtaW5lcyB0aGUgZXhpc3RlbmNlIG9mIGFuIG9kZCBjeWNsZSBpbiBhIGRpcmVjdGVkIGdyYXBoIGFuZCByZXBvcnQgYW4gYXJiaXRyYXJ5IG9kZCBjeWNsZSwgaWYgYW55LiZuYnNwOzxcL3A+XHJcblxyXG48cD5MZXQgRyBiZSBhIHNpbXBsZSBkaXJlY3RlZCBncmFwaCBoYXZpbmcgbm8gc2VsZi1sb29wcyBvciBtdWx0aXBsZSBlZGdlcy4gRm9yIGFueSB0d28gdmVydGljZXMgdiBhbmQgdyBvZiBHLCBhIChkaXJlY3RlZCkgcGF0aCBmcm9tIHYgdG8gdyBpbiBHIGlzIGEgc2VxdWVuY2UgKHU8c3ViPjE8XC9zdWI+LCB1PHN1Yj4yPFwvc3ViPiwgJmhlbGxpcDsgLHU8c3ViPmw8XC9zdWI+KSBvZiBkaXN0aW5jdCB2ZXJ0aWNlcyBvZiBHIHN1Y2ggdGhhdCB1PHN1Yj4xPFwvc3ViPiA9IHYsIHU8c3ViPmw8XC9zdWI+ID0gdywgYW5kIHU8c3ViPmk8XC9zdWI+IGlzIGFkamFjZW50IHRvIHU8c3ViPmkrMTxcL3N1Yj4gaW4gRyBmb3IgYWxsIGkgJmlzaW47IHsxLCAmaGVsbGlwOyAsIGwgJm1pbnVzOyAxfS4gSWYgbCAmZ2U7IDIgYW5kIHU8c3ViPmw8XC9zdWI+IGlzIGFkamFjZW50IHRvIHU8c3ViPjE8XC9zdWI+LCB0aGUgc2VxdWVuY2UgaXMgY2FsbGVkIGEgKGRpcmVjdGVkKSBjeWNsZS4gQW4gb2RkIGN5Y2xlIHJlZmVycyB0byBhIGN5Y2xlIG9mIG9kZCBsZW5ndGgsIHdoZXJlIHRoZSBsZW5ndGggb2YgYSBjeWNsZSBpcyBzaW1wbHkgdGhlIG51bWJlciBvZiBlZGdlcyBvZiB0aGUgY3ljbGUuIFJlZmVyIHRvIEZpZ3VyZSAxIGZvciBpbGx1c3RyYXRpdmUgZXhhbXBsZXMuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC8xMTQ5OFwvMS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMjJweDsgd2lkdGg6NTQzcHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPihhKSBUaGVyZSBpcyBubyBjeWNsZS4gKGIpIFRoZXJlIGlzIG5vIG9kZCBjeWNsZS4gKGMpIFRoZXJlIGlzIGFuIG9kZCBjeWNsZSAoMiwxLDMpLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+RmlndXJlIDEuIFNpbXBsZSBkaXJlY3RlZCBncmFwaHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLCB3aGVyZSB0aGUgcG9zaXRpdmUgaW50ZWdlciBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCwgZm9sbG93ZWQgYnkgdGhlIGRlc2NyaXB0aW9uIG9mIGVhY2ggdGVzdCBjYXNlLiBUaGUgZmlyc3QgbGluZSBvZiBhIHRlc3QgY2FzZSBjb250YWlucyB0d28gcG9zaXRpdmUgaW50ZWdlcnMgbiBhbmQgbSwgcmVzcGVjdGl2ZWx5LCBpbmRpY2F0aW5nIHRoZSBudW1iZXJzIG9mIHZlcnRpY2VzIGFuZCBkaXJlY3RlZCBlZGdlcyBpbiBhIHNpbXBsZSBkaXJlY3RlZCBncmFwaCwgaW4gd2hpY2ggd2UgYXNzdW1lIG4gJmxlOyAxMDAsMDAwIGFuZCBtICZsZTsgMSwwMDAsMDAwLiBUaGUgdmVydGljZXMgYXJlIGluZGV4ZWQgMSB0byBuLiBJbiB0aGUgZm9sbG93aW5nIDVsaW5lcywgZWFjaCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyB2IGFuZCB3LCB3aGljaCByZXByZXNlbnQgYSBkaXJlY3RlZCBlZGdlIGZyb20gdmVydGV4IHYgdG8gdmVydGV4IHcuIFRoZSB0d28gaW50ZWdlcnMgZ2l2ZW4gaW4gYSBzaW5nbGUgbGluZSBhcmUgYWx3YXlzIHNlcGFyYXRlZCBieSBhIHNwYWNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIEZvciBlYWNoIHRlc3QgY2FzZSwgdGhlIGZpcnN0IGxpbmUgbXVzdCBjb250YWluIGFuIGludGVnZXIgaW5kaWNhdGluZyB3aGV0aGVyIHRoZSBnaXZlbiBkaXJlY3RlZCBncmFwaCBoYXMgYW4gb2RkIGN5Y2xlLiBJZiB5ZXMsIHRoZSBpbnRlZ2VyIG11c3QgYmUgMTsgb3RoZXJ3aXNlIC0xLiBXaGVuIGFuZCBvbmx5IHdoZW4gdGhlIGZpcnN0IGxpbmUgaXMgMSwgaXQgbXVzdCBiZSBmb2xsb3dlZCBieSB0aGUgZGVzY3JpcHRpb24gb2YgYW4gYXJiaXRyYXJ5IG9kZCBjeWNsZSBvZiB0aGUgaW5wdXQgZ3JhcGguIEEgY3ljbGUgaXMgZGVzY3JpYmVkIGJ5IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBhbiBpbnRlZ2VyIGwsIHJlcHJlc2VudGluZyBpdHMgbGVuZ3RoLCBmb2xsb3dlZCBieSBsIGxpbmVzIGNvbnRhaW5pbmcsIG9uZSBieSBvbmUsIHRoZSB2ZXJ0aWNlcyBlbmNvdW50ZXJlZCB3aGVuIHdlIHRyYXZlcnNlIHRoZSBjeWNsZSBzdGFydGluZyBmcm9tIGFuIGFyYml0cmFyeSB2ZXJ0ZXguIE5vdGUgdGhhdCB0aGUgdmVydGljZXMgb2YgdGhlIGN5Y2xlIG11c3QgYmUgZGlzdGluY3QuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2015 F번