| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 61 | 15 | 12 | 29.268% |
표석이는 영생을 얻을 수 있다는 마녀의 물약을 구하기 위해 저주받은 숲으로 탐험을 떠났다.
저주받은 숲에는 1ドル$번부터 $N$번까지 번호가 붙은 $N$개의 나무가 있고, 나무와 나무 사이를 양방향으로 잇는 오솔길이 있다. 표석이는 $S$번 나무 아래에서 출발해서 오솔길을 따라 $E$번 나무 아래에 있는 마녀의 오두막까지 도달하는 길을 찾고자 한다.
저주받은 숲에는 기억을 잃게 만드는 저주가 걸려 있어, 한 번 발을 들인 탐험가는 평생을 헤매다가 끝내 자신조차 잃어버리게 된다는 전설이 전해진다. 탐험가가 $i$번 나무 아래에 도달한다면, $i$보다 작은 번호의 나무에 방문했던 기억은 흔적도 없이 사라진다.
표석이는 길을 잃지 않기 위해 한 가지 원칙을 세웠다.
”한 번 방문한 나무는 다시 방문하지 않는다.”
저주로 인해 방문했던 나무를 기억하지 못하고 다시 방문할 수도 있지만, 방문했던 사실을 기억하는 나무에는 절대 다시 발을 들이지 않을 것이다.
⋯⋯.
영겁의 시간이 기억 속에서 한순간에 스쳐 간다.
표석이는 마녀의 오두막 앞에 선, 낯선 노인을 발견하고 곧 그것이 자신임을 알아챈다.
그토록 갈망했던 영생은, 이제 낡은 육신 안에선 축복이 아닌 저주에 지나지 않으리라.
그저 묻고 싶은 것은, 얼마나 많은 세월이 덧없이 흘러가 버렸는가 하는 것뿐이다.
표석이는 지금 $E$번 나무 아래에 서 있다. 지금까지 방문한 나무들 중에서, 표석이가 기억하는 나무들의 번호가 주어진다. 이때, 지금까지 표석이가 오솔길을 따라 이동한 횟수로 가능한 최댓값을 구하여라. 단, 표석이는 $S$번이나 $E$번 나무를 여러 번 방문했을 수 있다. (저주로 인해 $S$번 나무에서 출발했다는 사실을 잊거나, $E$번 나무에서 마녀의 오두막을 발견하지 못하고 지나칠 수 있다.)
첫째 줄에 정수 $N,ドル $M,ドル $S,ドル $E$가 공백으로 구분되어 주어진다.
다음 $M$개의 줄에 오솔길이 잇는 두 나무의 번호 $a,ドル $b$가 공백으로 구분되어 주어진다. (1ドル\le a,b\le N$; $a\ne b$)
다음 줄에 표석이가 기억하는 방문한 나무의 개수 $K$가 주어진다. (1ドル\le K\le N$)
다음 줄에 표석이가 기억하는 방문한 나무들의 번호를 의미하는 $K$개의 정수가 공백으로 구분되어 주어진다. 번호는 감소하는 순으로 주어지며, 마지막 번호는 항상 $E$이다.
표석이가 마녀의 오두막에 도달하기까지 오솔길을 따라 이동한 횟수의 최댓값을 출력한다. 이동 경로는 $S$번 나무에서 출발하여 $E$번 나무까지 도달하는 경로여야 하며, 표석이의 기억과 일관되어야 한다.
만약 답이 10ドル^{18}$ 이상이라면 대신 eternity를 출력한다.
만약 조건에 맞는 경로가 존재하지 않으면 대신 impossible을 출력한다.
5 6 1 2 1 3 3 2 2 4 4 1 2 5 4 5 3 5 3 2
10
3 3 2 2 1 3 3 2 2 1 2 3 2
4
4 4 4 1 1 3 3 2 2 4 4 1 4 4 3 2 1
impossible
60 59 1 1 1 2 1 3 1 4 ... 1 58 1 59 1 60 60 60 59 58 ... 3 2 1
eternity
첫 번째 예제에서, 순서대로 1,3,2,4,1,3,2,5,2,3,2ドル$번 나무를 방문하는 것이 가장 이동 횟수가 많은 방법이다.
두 번째 예제에서, 순서대로 2,1,3,1,2ドル$번 나무를 방문하는 것이 가장 이동 횟수가 많은 방법이다.
세 번째 예제에서, 1ドル$번 나무에 도달하려면 반드시 3ドル$번이나 4ドル$번 나무를 거쳐야 하므로, 2ドル$번 나무를 방문한 사실을 기억하는 것이 불가능하다.
네 번째 예제는 각 오솔길이 1ドル$번 나무와 2,3,4,ドル\dots ,60$번 나무를 이으며, 모든 나무를 방문한 기억이 존재하는 예제이다. 가능한 이동 횟수의 최댓값이 10ドル^{18}$ 이상이므로 eternity를 출력한다.