시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 288 28 23 15.436%

문제

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

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+MjxcL3N1Yj4sICZoZWxsaXA7ICx1PHN1Yj5sPFwvc3ViPilcdWI3N2MgXHVkNTU4XHVjNzkwLiBcdWM3NzQgXHViNTRjLCB1PHN1Yj5pPFwvc3ViPlx1YjRlNFx1Yzc0MCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc0XHVhY2UwLCB1PHN1Yj4xPFwvc3ViPiA9IHYsIHU8c3ViPmw8XC9zdWI+ID0gd1x1Yzc3NFx1YWNlMCwgMVx1Yzc3NFx1YzBjMSBsIFx1YmJmOFx1YjljY1x1Yzc3OCBcdWJhYThcdWI0ZTAgaVx1YzVkMCBcdWIzMDBcdWQ1NzQgdTxzdWI+aTxcL3N1Yj5cdWM1ZDBcdWMxMWMgdTxzdWI+aSsxPFwvc3ViPlx1Yjg1YyBcdWFjMDBcdWIyOTQgXHViYzI5XHVkNWE1XHVjMTMxIFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBsICZnZTsgMlx1Yzc3NFx1YWNlMCB1PHN1Yj5sPFwvc3ViPlx1YzVkMFx1YzExYyB1PHN1Yj4xPFwvc3ViPlx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHViYzI5XHVkNWE1XHVjMTMxIFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTRcdWJhNzQsIFx1Yzc3NFx1Yjk3YyBcdWMyZjhcdWM3NzRcdWQwNzRcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWQ2NDBcdWMyMTggXHVjMmY4XHVjNzc0XHVkMDc0XHVjNzc0XHViNzgwIFx1YzJmOFx1Yzc3NFx1ZDA3NCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhZTM4XHVjNzc0IGxcdWM3NzQgXHVkNjQwXHVjMjE4XHVjNzc4IFx1YzJmOFx1Yzc3NFx1ZDA3NFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YzU0NFx1Yjc5OCAmbHQ7XHVhZGY4XHViOWJjIDEmZ3Q7XHVjNzQ0IFx1Y2MzOFx1YWNlMFx1ZDU1OFx1Yzc5MC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzExNDk4XC8xLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEyMnB4OyB3aWR0aDo1NDNweFwiIFwvPjxiciBcLz5cclxuJmx0O1x1YWRmOFx1YjliYyAxJmd0OyBcdWIyZThcdWMyMWMgXHViYzI5XHVkNWE1XHVjMTMxIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YjRlNDxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0IFx1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjNzkwXHVjNWYwXHVjMjE4IFRcdWFjMDAgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHVjNWI0XHVjMTFjIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM3OTBcdWM1ZjBcdWMyMTggTlx1YWNmYyBcdWFjMDRcdWMxMjBcdWM3NTggXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM3OTBcdWM1ZjBcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwIFx1YjllNFx1YWNhOFx1YzgzOFx1Yzc4OFx1YWNlMCwgTiAmbGU7IDEwMCwwMDAsIE0gJmxlOyAxLDAwMCwwMDBcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1ZDZjNCBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIyZThcdWMyMWMgXHViYzI5XHVkNWE1XHVjMTMxIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWFjMDRcdWMxMjBcdWI0ZTRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI5Y2NcdWM1N2QgdiB3XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1YjJlNFx1YmE3NCB2XHViYzg4IFx1YzgxNVx1YzgxMFx1YzVkMFx1YzExYyB3XHViYzg4IFx1YzgxNVx1YzgxMFx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHViYzI5XHVkNWE1XHVjMTMxIFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM3ODhcdWIyZTRcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1ZDY0MFx1YzIxOCBcdWMyZjhcdWM3NzRcdWQwNzRcdWM3NzQgXHVjNWM2XHVjNzNjXHViYTc0IC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCwgXHVjNzg4XHViMmU0XHViYTc0IDFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjIFx1YjRhNCBcdWMyZjhcdWM3NzRcdWQwNzRcdWM3NTggXHVkMDZjXHVhZTMwLCBcdWMyZjhcdWM3NzRcdWQwNzRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzgxNVx1YzgxMCBcdWJjODhcdWQ2MzhcdWI0ZTRcdWM3NDQgXHViYzI5XHViYjM4IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM5MDRcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjMmY4XHVjNzc0XHVkMDc0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWM4MTAgXHViYzg4XHVkNjM4XHViNGU0XHVjNzc0IFx1YzExY1x1Yjg1YyBcdWIyZWNcdWI3N2NcdWM1N2MgXHViNDI4XHVjNWQwIFx1YzcyMFx1Yzc1OFx1ZDU1OFx1Yzc5MC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMTQ5OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik9kZCBDeWNsZSIsImRlc2NyaXB0aW9uIjoiPHA+UmVjZW50bHksIGEgc21hcnQgc3R1ZGVudCBTZW9KaW4gcmVhbGl6ZWQgdGhhdCBub3QgYSBmZXcgaGFyZCBwcm9ibGVtcyBmb3IgZ2VuZXJhbCB1bmRpcmVjdGVkIGdyYXBocyBhcmUgcG9seW5vbWlhbGx5IHNvbHZhYmxlIGZvciBncmFwaHMgdGhhdCBoYXZlIG5vIGN5Y2xlcyBvZiBvZGQgbGVuZ3RoLiBXb25kZXJpbmcgd2hldGhlciBvciBub3QgdGhlIHNhbWUgZm9sbG93cyBmb3IgZGlyZWN0ZWQgZ3JhcGhzLCBzaGUgbWFkZSB1cCBoZXIgbWluZCB0byBzdGFydCBhIHN0dWR5IG9uIHRoZSBzdWJqZWN0IHVuZGVyIHRoZSBzdXBlcnZpc2lvbiBvZiBIeWVvbmdTZW9rLCBhIGRpc3Rpbmd1aXNoZWQgc2Nob2xhciBpbiB0aGlzIGZpZWxkLiBIZXIgZmlyc3QgcmVzZWFyY2ggZmluZGluZyBpcyBlZmZlY3RpdmUgcmVjb2duaXRpb24gb2YgdGhlIGRpcmVjdGVkIGdyYXBocyB3aXRob3V0IG9kZCBjeWNsZXMsIGkuZS4sIGFuIGFsZ29yaXRobSBmb3IgZGV0ZXJtaW5pbmcgaWYgYSBnaXZlbiBkaXJlY3RlZCBncmFwaCBoYXMgYSBjeWNsZSBvZiBvZGQgbGVuZ3RoLiBTdGlsbCwgc2hlIGlzIHByb21vdGluZyB1dG1vc3QgZWZmaWNpZW5jeSBpbiByZWNvZ25pemluZyBoZXIgY2xhc3Mgb2YgZ3JhcGhzLiBJbiBvcmRlciB0byBoZWxwIGhlciwgeW91IGFyZSBnb2luZyB0byB3cml0ZSBhbiB1bHRyYS1lZmZpY2llbnQgcHJvZ3JhbSB0aGF0IGRldGVybWluZXMgdGhlIGV4aXN0ZW5jZSBvZiBhbiBvZGQgY3ljbGUgaW4gYSBkaXJlY3RlZCBncmFwaCBhbmQgcmVwb3J0IGFuIGFyYml0cmFyeSBvZGQgY3ljbGUsIGlmIGFueS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TGV0IEcgYmUgYSBzaW1wbGUgZGlyZWN0ZWQgZ3JhcGggaGF2aW5nIG5vIHNlbGYtbG9vcHMgb3IgbXVsdGlwbGUgZWRnZXMuIEZvciBhbnkgdHdvIHZlcnRpY2VzIHYgYW5kIHcgb2YgRywgYSAoZGlyZWN0ZWQpIHBhdGggZnJvbSB2IHRvIHcgaW4gRyBpcyBhIHNlcXVlbmNlICh1PHN1Yj4xPFwvc3ViPiwgdTxzdWI+MjxcL3N1Yj4sICZoZWxsaXA7ICx1PHN1Yj5sPFwvc3ViPikgb2YgZGlzdGluY3QgdmVydGljZXMgb2YgRyBzdWNoIHRoYXQgdTxzdWI+MTxcL3N1Yj4gPSB2LCB1PHN1Yj5sPFwvc3ViPiA9IHcsIGFuZCB1PHN1Yj5pPFwvc3ViPiBpcyBhZGphY2VudCB0byB1PHN1Yj5pKzE8XC9zdWI+IGluIEcgZm9yIGFsbCBpICZpc2luOyB7MSwgJmhlbGxpcDsgLCBsICZtaW51czsgMX0uIElmIGwgJmdlOyAyIGFuZCB1PHN1Yj5sPFwvc3ViPiBpcyBhZGphY2VudCB0byB1PHN1Yj4xPFwvc3ViPiwgdGhlIHNlcXVlbmNlIGlzIGNhbGxlZCBhIChkaXJlY3RlZCkgY3ljbGUuIEFuIG9kZCBjeWNsZSByZWZlcnMgdG8gYSBjeWNsZSBvZiBvZGQgbGVuZ3RoLCB3aGVyZSB0aGUgbGVuZ3RoIG9mIGEgY3ljbGUgaXMgc2ltcGx5IHRoZSBudW1iZXIgb2YgZWRnZXMgb2YgdGhlIGN5Y2xlLiBSZWZlciB0byBGaWd1cmUgMSBmb3IgaWxsdXN0cmF0aXZlIGV4YW1wbGVzLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMTE0OThcLzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTIycHg7IHdpZHRoOjU0M3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj4oYSkgVGhlcmUgaXMgbm8gY3ljbGUuIChiKSBUaGVyZSBpcyBubyBvZGQgY3ljbGUuIChjKSBUaGVyZSBpcyBhbiBvZGQgY3ljbGUgKDIsMSwzKS48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPkZpZ3VyZSAxLiBTaW1wbGUgZGlyZWN0ZWQgZ3JhcGhzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcywgd2hlcmUgdGhlIHBvc2l0aXZlIGludGVnZXIgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQsIGZvbGxvd2VkIGJ5IHRoZSBkZXNjcmlwdGlvbiBvZiBlYWNoIHRlc3QgY2FzZS4gVGhlIGZpcnN0IGxpbmUgb2YgYSB0ZXN0IGNhc2UgY29udGFpbnMgdHdvIHBvc2l0aXZlIGludGVnZXJzIG4gYW5kIG0sIHJlc3BlY3RpdmVseSwgaW5kaWNhdGluZyB0aGUgbnVtYmVycyBvZiB2ZXJ0aWNlcyBhbmQgZGlyZWN0ZWQgZWRnZXMgaW4gYSBzaW1wbGUgZGlyZWN0ZWQgZ3JhcGgsIGluIHdoaWNoIHdlIGFzc3VtZSBuICZsZTsgMTAwLDAwMCBhbmQgbSAmbGU7IDEsMDAwLDAwMC4gVGhlIHZlcnRpY2VzIGFyZSBpbmRleGVkIDEgdG8gbi4gSW4gdGhlIGZvbGxvd2luZyA1bGluZXMsIGVhY2ggbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgdiBhbmQgdywgd2hpY2ggcmVwcmVzZW50IGEgZGlyZWN0ZWQgZWRnZSBmcm9tIHZlcnRleCB2IHRvIHZlcnRleCB3LiBUaGUgdHdvIGludGVnZXJzIGdpdmVuIGluIGEgc2luZ2xlIGxpbmUgYXJlIGFsd2F5cyBzZXBhcmF0ZWQgYnkgYSBzcGFjZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBGb3IgZWFjaCB0ZXN0IGNhc2UsIHRoZSBmaXJzdCBsaW5lIG11c3QgY29udGFpbiBhbiBpbnRlZ2VyIGluZGljYXRpbmcgd2hldGhlciB0aGUgZ2l2ZW4gZGlyZWN0ZWQgZ3JhcGggaGFzIGFuIG9kZCBjeWNsZS4gSWYgeWVzLCB0aGUgaW50ZWdlciBtdXN0IGJlIDE7IG90aGVyd2lzZSAtMS4gV2hlbiBhbmQgb25seSB3aGVuIHRoZSBmaXJzdCBsaW5lIGlzIDEsIGl0IG11c3QgYmUgZm9sbG93ZWQgYnkgdGhlIGRlc2NyaXB0aW9uIG9mIGFuIGFyYml0cmFyeSBvZGQgY3ljbGUgb2YgdGhlIGlucHV0IGdyYXBoLiBBIGN5Y2xlIGlzIGRlc2NyaWJlZCBieSBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciBsLCByZXByZXNlbnRpbmcgaXRzIGxlbmd0aCwgZm9sbG93ZWQgYnkgbCBsaW5lcyBjb250YWluaW5nLCBvbmUgYnkgb25lLCB0aGUgdmVydGljZXMgZW5jb3VudGVyZWQgd2hlbiB3ZSB0cmF2ZXJzZSB0aGUgY3ljbGUgc3RhcnRpbmcgZnJvbSBhbiBhcmJpdHJhcnkgdmVydGV4LiBOb3RlIHRoYXQgdGhlIHZlcnRpY2VzIG9mIHRoZSBjeWNsZSBtdXN0IGJlIGRpc3RpbmN0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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