시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB228665329.944%

문제

현성이가 자신의 형 현민이와 게임을 한다. 이 게임은 특정한 맵에서 진행된다.

이 게임에서 사용하는 맵은 N개의 원과 M개의 화살표가 그려져 있는데, 각 화살표는 서로 다른 두 원을 연결하고 있다.

게임을 시작하면, 맨 처음에 말은 1번째 원 위에 있다. 매 턴마다 현민이가 1 이상의 정수를 말한다. 그런 후에는 현성이가 현민이가 말한 수만큼 말을 움직인다. 말은 오직 화살표 방향으로만 이동할 수 있다.

현성이가 말을 움직여서 N번째 원 위로 도착하면 현성이가 이긴다. 다만, 현성이가 말을 더 움직여야 하는 상황에서 N번째 원으로 온 경우는 게임이 끝나지 않는다. 만약 현성이가 말을 움직이다가 더 이상 말을 움직일 수 없는 상황이 온 경우 현민이가 이긴다. 또, 게임이 무한히 반복된다면 현민이의 승리로 간주한다.

현민이는 두뇌 서바이벌 프로그램에서 준우승할 정도로 똑똑하기 때문에 게임을 할 때마다 계속 현민이가 이겼다. 그래서 현민이는 현성이의 멘탈을 위해 조금 봐주기로 했다. 현민이는 현성이를 위해 매 턴을 시작할 때 부르는 수를 a, b, c 중에서 고르기로 했다. 그래도 현성이가 현민이를 이기기에는 역부족이었다.

멘탈이 증발한 현성이는 당신에게 현민이를 이기는 전략을 짜달라고 요청하였다. 현성이를 도와 현민이를 이기는 전략이 있는지 구하고 만약 있다면 최소 몇 턴만에 게임을 끝낼 수 있는지 구하여라.

입력

첫 번째 줄에는 N, M, a, b, c가 주어진다. N은 원의 개수, M은 화살표의 개수, a, b, c는 현민이가 부르는 수를 의미한다. (2 ≤ N ≤ 50, 0 ≤ M ≤ N(N-1), 1 ≤ a, b, c ≤ 100)

두 번째 줄부터 M개의 줄에는 각 화살표의 시작점, 끝점 u, v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 어떤 두 화살표에 대해서도 시작점과 끝점이 완전히 같지는 않다.

출력

만약 현성이가 현민이를 이길 수 없다면 'IMPOSSIBLE'을 출력한다.

그렇지 않은 경우, 현성이가 현민이를 이기기 위해 필요한 최소 턴의 수를 출력한다.

예제 입력 1

3 3 1 2 4
1 2
2 3
3 1

예제 출력 1

IMPOSSIBLE

예제 입력 2

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

예제 출력 2

2

힌트

첫 번째 예제에서는 현민이가 1, 2를 번갈아 부르면 게임이 끝나지 않기 때문에 현민이가 이긴다.

두 번째 예제에서는 아래와 같은 전략을 세우면 된다.

  • 만약 현민이가 2나 3을 부른다면 한 번만에 N번 원으로 갈 수 있다.
  • 만약 현민이가 1을 부른다면 4번 원으로 가는 것이 최적이다. 현성이가 4번 원으로 간다면 현민이가 다음 턴에 무슨 수를 부르던지 한 번에 N번 원으로 갈 수 있다. 만약 현성이가 5번 원으로 간다면 현민이가 2나 3을 부르면 현민이가 이긴다. 현성이가 2번 원으로 간다면 현성이가 이길 수는 있지만 더 많은 턴을 요구한다.

두 번째 예제의 맵

W3sicHJvYmxlbV9pZCI6IjExNzQ5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNjE1XHVjODFjIFx1YWM4Y1x1Yzc4NCIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNjA0XHVjMTMxXHVjNzc0XHVhYzAwIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWQ2MTUgXHVkNjA0XHViYmZjXHVjNzc0XHVjNjQwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDAgXHVkMmI5XHVjODE1XHVkNTVjIFx1YjlmNVx1YzVkMFx1YzExYyBcdWM5YzRcdWQ1ODlcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM1ZDBcdWMxMWMgXHVjMGFjXHVjNmE5XHVkNTU4XHViMjk0IFx1YjlmNVx1Yzc0MCBOXHVhYzFjXHVjNzU4IFx1YzZkMFx1YWNmYyBNXHVhYzFjXHVjNzU4IFx1ZDY1NFx1YzBiNFx1ZDQ1Y1x1YWMwMCBcdWFkZjhcdWI4MjRcdWM4MzggXHVjNzg4XHViMjk0XHViMzcwLCBcdWFjMDEgXHVkNjU0XHVjMGI0XHVkNDVjXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViNDUwIFx1YzZkMFx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjOGNcdWM3ODRcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHViYTc0LCBcdWI5ZTggXHVjYzk4XHVjNzRjXHVjNWQwIFx1YjlkMFx1Yzc0MCAxXHViYzg4XHVjOWY4IFx1YzZkMCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMmU0LiBcdWI5ZTQgXHVkMTM0XHViOWM4XHViMmU0IFx1ZDYwNFx1YmJmY1x1Yzc3NFx1YWMwMCAxIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWM4MTVcdWMyMThcdWI5N2MgXHViOWQwXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3ZjAgXHVkNmM0XHVjNWQwXHViMjk0IFx1ZDYwNFx1YzEzMVx1Yzc3NFx1YWMwMCBcdWQ2MDRcdWJiZmNcdWM3NzRcdWFjMDAgXHViOWQwXHVkNTVjIFx1YzIxOFx1YjljY1x1ZDA3YyBcdWI5ZDBcdWM3NDQgXHVjNmMwXHVjOWMxXHVjNzc4XHViMmU0LiBcdWI5ZDBcdWM3NDAgXHVjNjI0XHVjOWMxIFx1ZDY1NFx1YzBiNFx1ZDQ1YyBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWNcdWI5Y2MgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDYwNFx1YzEzMVx1Yzc3NFx1YWMwMCBcdWI5ZDBcdWM3NDQgXHVjNmMwXHVjOWMxXHVjNWVjXHVjMTFjIE5cdWJjODhcdWM5ZjggXHVjNmQwIFx1YzcwNFx1Yjg1YyBcdWIzYzRcdWNjMjlcdWQ1NThcdWJhNzQgXHVkNjA0XHVjMTMxXHVjNzc0XHVhYzAwIFx1Yzc3NFx1YWUzNFx1YjJlNC4gXHViMmU0XHViOWNjLCBcdWQ2MDRcdWMxMzFcdWM3NzRcdWFjMDAgXHViOWQwXHVjNzQ0IFx1YjM1NCBcdWM2YzBcdWM5YzFcdWM1ZWNcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzBjMVx1ZDY2OVx1YzVkMFx1YzExYyBOXHViYzg4XHVjOWY4IFx1YzZkMFx1YzczY1x1Yjg1YyBcdWM2MjggXHVhY2JkXHVjNmIwXHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWIwNWRcdWIwOThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVkNjA0XHVjMTMxXHVjNzc0XHVhYzAwIFx1YjlkMFx1Yzc0NCBcdWM2YzBcdWM5YzFcdWM3NzRcdWIyZTRcdWFjMDAgXHViMzU0IFx1Yzc3NFx1YzBjMSBcdWI5ZDBcdWM3NDQgXHVjNmMwXHVjOWMxXHVjNzdjIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVjMGMxXHVkNjY5XHVjNzc0IFx1YzYyOCBcdWFjYmRcdWM2YjAgXHVkNjA0XHViYmZjXHVjNzc0XHVhYzAwIFx1Yzc3NFx1YWUzNFx1YjJlNC4gXHViNjEwLCBcdWFjOGNcdWM3ODRcdWM3NzQgXHViYjM0XHVkNTVjXHVkNzg4IFx1YmMxOFx1YmNmNVx1YjQxY1x1YjJlNFx1YmE3NCBcdWQ2MDRcdWJiZmNcdWM3NzRcdWM3NTggXHVjMmI5XHViOWFjXHViODVjIFx1YWMwNFx1YzhmY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNjA0XHViYmZjXHVjNzc0XHViMjk0IFx1YjQ1MFx1YjFjYyBcdWMxMWNcdWJjMTRcdWM3NzRcdWJjOGMgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNWQwXHVjMTFjIFx1YzkwMFx1YzZiMFx1YzJiOVx1ZDU2MCBcdWM4MTVcdWIzYzRcdWI4NWMgXHViNjExXHViNjExXHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTYwIFx1YjU0Y1x1YjljOFx1YjJlNCBcdWFjYzRcdWMxOGQgXHVkNjA0XHViYmZjXHVjNzc0XHVhYzAwIFx1Yzc3NFx1YWNiY1x1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1ZDYwNFx1YmJmY1x1Yzc3NFx1YjI5NCBcdWQ2MDRcdWMxMzFcdWM3NzRcdWM3NTggXHViYTU4XHVkMGM4XHVjNzQ0IFx1YzcwNFx1ZDU3NCBcdWM4NzBcdWFlMDggXHViZDEwXHVjOGZjXHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC4gXHVkNjA0XHViYmZjXHVjNzc0XHViMjk0IFx1ZDYwNFx1YzEzMVx1Yzc3NFx1Yjk3YyBcdWM3MDRcdWQ1NzQgXHViOWU0IFx1ZDEzNFx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NjAgXHViNTRjIFx1YmQ4MFx1Yjk3NFx1YjI5NCBcdWMyMThcdWI5N2MgYSwgYiwgYyBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhY2UwXHViOTc0XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC4gXHVhZGY4XHViNzk4XHViM2M0IFx1ZDYwNFx1YzEzMVx1Yzc3NFx1YWMwMCBcdWQ2MDRcdWJiZmNcdWM3NzRcdWI5N2MgXHVjNzc0XHVhZTMwXHVhZTMwXHVjNWQwXHViMjk0IFx1YzVlZFx1YmQ4MFx1Yzg3MVx1Yzc3NFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYTU4XHVkMGM4XHVjNzc0IFx1Yzk5ZFx1YmMxY1x1ZDU1YyBcdWQ2MDRcdWMxMzFcdWM3NzRcdWIyOTQgXHViMmY5XHVjMmUwXHVjNWQwXHVhYzhjIFx1ZDYwNFx1YmJmY1x1Yzc3NFx1Yjk3YyBcdWM3NzRcdWFlMzBcdWIyOTQgXHVjODA0XHViN2I1XHVjNzQ0IFx1YzlkY1x1YjJlY1x1Yjc3Y1x1YWNlMCBcdWM2OTRcdWNjYWRcdWQ1NThcdWM2MDBcdWIyZTQuIFx1ZDYwNFx1YzEzMVx1Yzc3NFx1Yjk3YyBcdWIzYzRcdWM2NDAgXHVkNjA0XHViYmZjXHVjNzc0XHViOTdjIFx1Yzc3NFx1YWUzMFx1YjI5NCBcdWM4MDRcdWI3YjVcdWM3NzQgXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YWNlMCBcdWI5Y2NcdWM1N2QgXHVjNzg4XHViMmU0XHViYTc0IFx1Y2Q1Y1x1YzE4YyBcdWJhODcgXHVkMTM0XHViOWNjXHVjNWQwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWIwNWRcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOLCBNLCBhLCBiLCBjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gTlx1Yzc0MCBcdWM2ZDBcdWM3NTggXHVhYzFjXHVjMjE4LCBNXHVjNzQwIFx1ZDY1NFx1YzBiNFx1ZDQ1Y1x1Yzc1OCBcdWFjMWNcdWMyMTgsIGEsIGIsIGNcdWIyOTQgXHVkNjA0XHViYmZjXHVjNzc0XHVhYzAwIFx1YmQ4MFx1Yjk3NFx1YjI5NCBcdWMyMThcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiAoMiAmbGU7IE4gJmxlOyA1MCwgMCAmbGU7IE0gJmxlOyBOKE4tMSksIDEgJmxlOyBhLCBiLCBjICZsZTsgMTAwKTxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVkNjU0XHVjMGI0XHVkNDVjXHVjNzU4IFx1YzJkY1x1Yzc5MVx1YzgxMCwgXHViMDVkXHVjODEwIHUsIHZcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IHUsIHYgJmxlOyBOLCB1ICZuZTsgdikgXHVjNWI0XHViNWE0IFx1YjQ1MCBcdWQ2NTRcdWMwYjRcdWQ0NWNcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjXHViM2M0IFx1YzJkY1x1Yzc5MVx1YzgxMFx1YWNmYyBcdWIwNWRcdWM4MTBcdWM3NzQgXHVjNjQ0XHVjODA0XHVkNzg4IFx1YWMxOVx1YzljMFx1YjI5NCBcdWM1NGFcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViOWNjXHVjNTdkIFx1ZDYwNFx1YzEzMVx1Yzc3NFx1YWMwMCBcdWQ2MDRcdWJiZmNcdWM3NzRcdWI5N2MgXHVjNzc0XHVhZTM4IFx1YzIxOCBcdWM1YzZcdWIyZTRcdWJhNzQgJiMzOTtJTVBPU1NJQkxFJiMzOTtcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI4MDdcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YWNiZFx1YzZiMCwgXHVkNjA0XHVjMTMxXHVjNzc0XHVhYzAwIFx1ZDYwNFx1YmJmY1x1Yzc3NFx1Yjk3YyBcdWM3NzRcdWFlMzBcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGMgXHVkMTM0XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjNjA4XHVjODFjXHVjNWQwXHVjMTFjXHViMjk0IFx1ZDYwNFx1YmJmY1x1Yzc3NFx1YWMwMCAxLCAyXHViOTdjIFx1YmM4OFx1YWMwOFx1YzU0NCBcdWJkODBcdWI5NzRcdWJhNzQgXHVhYzhjXHVjNzg0XHVjNzc0IFx1YjA1ZFx1YjA5OFx1YzljMCBcdWM1NGFcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1ZDYwNFx1YmJmY1x1Yzc3NFx1YWMwMCBcdWM3NzRcdWFlMzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjNjA4XHVjODFjXHVjNWQwXHVjMTFjXHViMjk0IFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjODA0XHViN2I1XHVjNzQ0IFx1YzEzOFx1YzZiMFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHViOWNjXHVjNTdkIFx1ZDYwNFx1YmJmY1x1Yzc3NFx1YWMwMCAyXHViMDk4IDNcdWM3NDQgXHViZDgwXHViOTc4XHViMmU0XHViYTc0IFx1ZDU1YyBcdWJjODhcdWI5Y2NcdWM1ZDAgTlx1YmM4OCBcdWM2ZDBcdWM3M2NcdWI4NWMgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjljY1x1YzU3ZCBcdWQ2MDRcdWJiZmNcdWM3NzRcdWFjMDAgMVx1Yzc0NCBcdWJkODBcdWI5NzhcdWIyZTRcdWJhNzQgNFx1YmM4OCBcdWM2ZDBcdWM3M2NcdWI4NWMgXHVhYzAwXHViMjk0IFx1YWM4M1x1Yzc3NCBcdWNkNWNcdWM4MDFcdWM3NzRcdWIyZTQuIFx1ZDYwNFx1YzEzMVx1Yzc3NFx1YWMwMCA0XHViYzg4IFx1YzZkMFx1YzczY1x1Yjg1YyBcdWFjMDRcdWIyZTRcdWJhNzQgXHVkNjA0XHViYmZjXHVjNzc0XHVhYzAwIFx1YjJlNFx1Yzc0YyBcdWQxMzRcdWM1ZDAgXHViYjM0XHVjMmE4IFx1YzIxOFx1Yjk3YyBcdWJkODBcdWI5NzRcdWIzNThcdWM5YzAgXHVkNTVjIFx1YmM4OFx1YzVkMCBOXHViYzg4IFx1YzZkMFx1YzczY1x1Yjg1YyBcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViOWNjXHVjNTdkIFx1ZDYwNFx1YzEzMVx1Yzc3NFx1YWMwMCA1XHViYzg4IFx1YzZkMFx1YzczY1x1Yjg1YyBcdWFjMDRcdWIyZTRcdWJhNzQgXHVkNjA0XHViYmZjXHVjNzc0XHVhYzAwIDJcdWIwOTggM1x1Yzc0NCBcdWJkODBcdWI5NzRcdWJhNzQgXHVkNjA0XHViYmZjXHVjNzc0XHVhYzAwIFx1Yzc3NFx1YWUzNFx1YjJlNC4gXHVkNjA0XHVjMTMxXHVjNzc0XHVhYzAwIDJcdWJjODggXHVjNmQwXHVjNzNjXHViODVjIFx1YWMwNFx1YjJlNFx1YmE3NCBcdWQ2MDRcdWMxMzFcdWM3NzRcdWFjMDAgXHVjNzc0XHVhZTM4IFx1YzIxOFx1YjI5NCBcdWM3ODhcdWM5YzBcdWI5Y2MgXHViMzU0IFx1YjljZVx1Yzc0MCBcdWQxMzRcdWM3NDQgXHVjNjk0XHVhZDZjXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzExNzQ5XC8xLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIwM3B4OyBsaW5lLWhlaWdodDoyMC44cHg7IG9wYWNpdHk6MC45OyB0ZXh0LWFsaWduOmNlbnRlcjsgd2lkdGg6MjE5cHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM2MDhcdWM4MWNcdWM3NTggXHViOWY1PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMTc0OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNpYmxpbmcgUml2YWxyeSIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBwbGF5aW5nIGEgZ2FtZSB3aXRoIHlvdXIgZWxkZXIgYnJvdGhlci48XC9wPlxyXG5cclxuPHA+Rmlyc3QsIGEgbnVtYmVyIG9mIGNpcmNsZXMgYW5kIGFycm93cyBjb25uZWN0aW5nIHNvbWUgcGFpcnMgb2YgdGhlIGNpcmNsZXMgYXJlIGRyYXduIG9uIHRoZSBncm91bmQuIFR3byBvZiB0aGUgY2lyY2xlcyBhcmUgbWFya2VkIGFzIHRoZSBzdGFydCBjaXJjbGUgYW5kIHRoZSBnb2FsIGNpcmNsZS48XC9wPlxyXG5cclxuPHA+QXQgdGhlIHN0YXJ0IG9mIHRoZSBnYW1lLCB5b3UgYXJlIG9uIHRoZSBzdGFydCBjaXJjbGUuIEluIGVhY2ggdHVybiBvZiB0aGUgZ2FtZSwgeW91ciBicm90aGVyIHRlbGxzIHlvdSBhIG51bWJlciwgYW5kIHlvdSBoYXZlIHRvIHRha2UgdGhhdCBudW1iZXIgb2Ygc3RlcHMuIEF0IGVhY2ggc3RlcCwgeW91IGNob29zZSBvbmUgb2YgdGhlIGFycm93cyBvdXRnb2luZyBmcm9tIHRoZSBjaXJjbGUgeW91IGFyZSBvbiwgYW5kIG1vdmUgdG8gdGhlIGNpcmNsZSB0aGUgYXJyb3cgaXMgaGVhZGluZyB0by4gWW91IGNhbiB2aXNpdCB0aGUgc2FtZSBjaXJjbGUgb3IgdXNlIHRoZSBzYW1lIGFycm93IGFueSBudW1iZXIgb2YgdGltZXMuPFwvcD5cclxuXHJcbjxwPllvdXIgYWltIGlzIHRvIHN0b3Agb24gdGhlIGdvYWwgY2lyY2xlIGFmdGVyIHRoZSBmZXdlc3QgcG9zc2libGUgdHVybnMsIHdoaWxlIHlvdXIgYnJvdGhlciZyc3F1bztzIGFpbSBpcyB0byBwcmV2ZW50IGl0IGFzIGxvbmcgYXMgcG9zc2libGUuIE5vdGUgdGhhdCwgaW4gZWFjaCBzaW5nbGUgdHVybiwgeW91IG11c3QgdGFrZSB0aGUgZXhhY3QgbnVtYmVyIG9mIHN0ZXBzIHlvdXIgYnJvdGhlciB0ZWxscyB5b3UuIEV2ZW4gd2hlbiB5b3UgdmlzaXQgdGhlIGdvYWwgY2lyY2xlIGR1cmluZyBhIHR1cm4sIHlvdSBoYXZlIHRvIGxlYXZlIGl0IGlmIG1vcmUgc3RlcHMgYXJlIHRvIGJlIHRha2VuLjxcL3A+XHJcblxyXG48cD5JZiB5b3UgcmVhY2ggYSBjaXJjbGUgd2l0aCBubyBvdXRnb2luZyBhcnJvd3MgYmVmb3JlIGNvbXBsZXRpbmcgYWxsIHRoZSBzdGVwcywgdGhlbiB5b3UgbG9zZSB0aGUgZ2FtZS4gWW91IGFsc28gaGF2ZSB0byBub3RlIHRoYXQsIHlvdXIgYnJvdGhlciBtYXkgYmUgYWJsZSB0byByZXBlYXQgdHVybnMgZm9yZXZlciwgbm90IGFsbG93aW5nIHlvdSB0byBzdG9wIGFmdGVyIGFueSBvZiB0aGVtLjxcL3A+XHJcblxyXG48cD5Zb3VyIGJyb3RoZXIsIG1lYW4gYnV0IG5vdCB0b28gc2VsZmlzaCwgdGhvdWdodCB0aGF0IGJlaW5nIGFsbG93ZWQgdG8gY2hvb3NlIGFyYml0cmFyeSBudW1iZXJzIGlzIG5vdCBmYWlyLiBTbywgaGUgZGVjaWRlZCB0byBkZWNsYXJlIHRocmVlIG51bWJlcnMgYXQgdGhlIHN0YXJ0IG9mIHRoZSBnYW1lIGFuZCB0byB1c2Ugb25seSB0aG9zZSBudW1iZXJzLjxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgbm93IGlzLCBnaXZlbiB0aGUgY29uZmlndXJhdGlvbiBvZiBjaXJjbGVzIGFuZCBhcnJvd3MsIGFuZCB0aGUgdGhyZWUgbnVtYmVycyBkZWNsYXJlZCwgdG8gY29tcHV0ZSB0aGUgc21hbGxlc3QgcG9zc2libGUgbnVtYmVyIG9mIHR1cm5zIHdpdGhpbiB3aGljaCB5b3UgY2FuIGFsd2F5cyBmaW5pc2ggdGhlIGdhbWUsIG5vIG1hdHRlciBob3cgeW91ciBicm90aGVyIGNob29zZXMgdGhlIG51bWJlcnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgYSBzaW5nbGUgdGVzdCBjYXNlLCBmb3JtYXR0ZWQgYXMgZm9sbG93cy48XC9wPlxyXG5cclxuPHByZT5cclxubiBtIGEgYiBjXHJcbnU8c3ViPjE8XC9zdWI+IHY8c3ViPjE8XC9zdWI+XHJcbi5cclxuLlxyXG4uXHJcbnU8c3ViPm08XC9zdWI+IHY8c3ViPm08XC9zdWI+PFwvcHJlPlxyXG5cclxuPHA+QWxsIG51bWJlcnMgaW4gYSB0ZXN0IGNhc2UgYXJlIGludGVnZXJzLiBuIGlzIHRoZSBudW1iZXIgb2YgY2lyY2xlcyAoMiAmbGU7IG4gJmxlOyA1MCkuIENpcmNsZXMgYXJlIG51bWJlcmVkIDEgdGhyb3VnaCBuLiBUaGUgc3RhcnQgYW5kIGdvYWwgY2lyY2xlcyBhcmUgbnVtYmVyZWQgMSBhbmQgbiwgcmVzcGVjdGl2ZWx5LiBtIGlzIHRoZSBudW1iZXIgb2YgYXJyb3dzICgwICZsZTsgbSAmbGU7IG4obiAmbWludXM7IDEpKS4gYSwgYiwgYW5kIGMgYXJlIHRoZSB0aHJlZSBudW1iZXJzIHlvdXIgYnJvdGhlciBkZWNsYXJlZCAoMSAmbGU7IGEsIGIsIGMgJmxlOyAxMDApLiBUaGUgcGFpciwgdTxzdWI+aTxcL3N1Yj4gYW5kIHY8c3ViPmk8XC9zdWI+LCBtZWFucyB0aGF0IHRoZXJlIGlzIGFuIGFycm93IGZyb20gdGhlIGNpcmNsZSB1PHN1Yj5pPFwvc3ViPiB0byB0aGUgY2lyY2xlIHY8c3ViPmk8XC9zdWI+LiBJdCBpcyBlbnN1cmVkIHRoYXQgdTxzdWI+aTxcL3N1Yj4gJm5lOyB2PHN1Yj5pPFwvc3ViPiBmb3IgYWxsIGksIGFuZCB1PHN1Yj5pPFwvc3ViPiAmbmU7IHU8c3ViPmo8XC9zdWI+IG9yIHY8c3ViPmk8XC9zdWI+ICZuZTsgdjxzdWI+ajxcL3N1Yj4gaWYgaSAmbmU7IGouPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgdGhlIHNtYWxsZXN0IHBvc3NpYmxlIG51bWJlciBvZiB0dXJucyB3aXRoaW4gd2hpY2ggeW91IGNhbiBhbHdheXMgZmluaXNoIHRoZSBnYW1lLiBQcmludCBJTVBPU1NJQkxFIGlmIHlvdXIgYnJvdGhlciBjYW4gcHJldmVudCB5b3UgZnJvbSByZWFjaGluZyB0aGUgZ29hbCwgYnkgZWl0aGVyIG1ha2luZyB5b3UgcmVwZWF0IHRoZSB0dXJucyBmb3JldmVyIG9yIGxlYWRpbmcgeW91IHRvIGEgY2lyY2xlIHdpdGhvdXQgb3V0Z29pbmcgYXJyb3dzLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5Gb3IgU2FtcGxlIElucHV0IDEsIHlvdXIgYnJvdGhlciBtYXkgY2hvb3NlIDEgZmlyc3QsIHRoZW4gMiwgYW5kIHJlcGVhdCB0aGVzZSBmb3JldmVyLiBUaGVuIHlvdSBjYW4gbmV2ZXIgZmluaXNoLjxcL3A+XHJcblxyXG48cD5Gb3IgU2FtcGxlIElucHV0IDIgKEZpZ3VyZSBDLjEpLCBpZiB5b3VyIGJyb3RoZXIgY2hvb3NlcyAyIG9yIDMsIHlvdSBjYW4gZmluaXNoIHdpdGggYSBzaW5nbGUgdHVybi4gSWYgaGUgY2hvb3NlcyAxLCB5b3Ugd2lsbCBoYXZlIHRocmVlIG9wdGlvbnMuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+TW92ZSB0byB0aGUgY2lyY2xlIDUuIFRoaXMgaXMgYSBiYWQgaWRlYTogWW91ciBicm90aGVyIG1heSB0aGVuIGNob29zZSAyIG9yIDMgYW5kIG1ha2UgeW91IGxvc2UuPFwvbGk+XHJcblx0PGxpPk1vdmUgdG8gdGhlIGNpcmNsZSA0LiBUaGlzIGlzIHRoZSBiZXN0IGNob2ljZTogRnJvbSB0aGUgY2lyY2xlIDQsIG5vIG1hdHRlciBhbnkgb2YgMSwgMiwgb3IgMyB5b3VyIGJyb3RoZXIgY2hvb3NlcyBpbiB0aGUgbmV4dCB0dXJuLCB5b3UgY2FuIGZpbmlzaCBpbW1lZGlhdGVseTxcL2xpPlxyXG5cdDxsaT5Nb3ZlIHRvIHRoZSBjaXJjbGUgMi4gVGhpcyBpcyBub3Qgb3B0aW1hbCBmb3IgeW91LiBJZiB5b3VyIGJyb3RoZXIgY2hvb3NlcyAxIGluIHRoZSBuZXh0IHR1cm4sIHlvdSBjYW5ub3QgZmluaXNoIHlldC4gSXQgd2lsbCB0YWtlIHRocmVlIG9yIG1vcmUgdHVybnMgaW4gdG90YWwuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SW4gc3VtbWFyeSwgbm8gbWF0dGVyIGhvdyB5b3VyIGJyb3RoZXIgYWN0cywgeW91IGNhbiBmaW5pc2ggd2l0aGluIHR3byB0dXJucy4gVGh1cyB0aGUgYW5zd2VyIGlzIDIuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzExNzQ5XC8xLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIwM3B4OyB3aWR0aDoyMTlweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5GaWd1cmUgQy4xLiBTYW1wbGUgSW5wdXQgMjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Asia Pacific > Japan > Asia Regional Contest 2015 in Tsukuba C번