시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 38 11 10 32.258%

문제

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

이 게임에서 사용하는 맵은 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 ≤ 100) 어떤 두 화살표에 대해서도 시작점과 끝점이 완전히 같지는 않다.

출력

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

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

예제 입력

3 3 1 2 4
1 2
2 3
3 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번 원으로 간다면 현성이가 이길 수는 있지만 더 많은 턴을 요구한다.

두 번째 예제의 맵