빔으로 탈출!
시간 제한1초메모리 제한256 MB
1번 방에서 시작하는 무작위 이동이 n번 방에 확실히 도달하는지와 모든 가능한 이동이 제한된 단계 안에 끝나는지를 판단합니다.
문제
리마크 왕은 관대해서, 죄를 뉘우친 죄인에게 대미로에서 두 번째 기회를 준다.
오늘의 죄인은 이름난 컴퓨터 과학자다. 리마크 왕이 고안한 무작위 알고리즘을 연구하라는 명을 거절한 탓에 명성은 아무 도움이 되지 않았다. 그 알고리즘은 아주 오래 돌 수도 있고, 아예 끝나지 않을 수도 있으며, 끝난다 해도 정답을 내놓는다는 보장이 없다.
대미로는 최근 최신 빔 전송 기술로 개조되어 문이 모두 필요 없어졌다. 죄인이 "제가 틀렸습니다. 다시는 리마크 왕을 실망시키지 않겠습니다!"라는 주문을 외우면 즉시 다음 방으로 전송된다. 전송될 방은 지금 있는 방에 적힌 목표 방 목록에서 무작위로 하나 정해진다.
대미로에는 번부터 번까지 번호가 붙은 방 개가 있다. 죄인은 모두 번 방에서 출발하고, 왕좌의 방인 번 방에 도달하면 사면을 받는다. 목표 방 목록이 비어 있는 방에 들어가면 여정은 거기서 끝난다. 그 방에서 주문을 몇 번 더 외워도 손해는 없지만 도움도 되지 않는다.
리마크 왕은 놀라는 일을 싫어해서 두 가지를 묻는다. 죄인이 왕좌의 방에 도달하는 것이 보장되는가, 그리고 전송 횟수에 상한이 있어서 언젠가 반드시 게임이 끝나는가.
목록에 적힌 방은 각각 보다 큰 확률로 뽑힌다.
입력
입력은 테스트 케이스 하나로 이루어진다.
첫 줄에 대미로의 방 개수 이 주어진다. ()
이어서 번 방부터 번 방까지 순서대로, 각 방마다 두 줄이 주어진다. 왕좌의 방인 번 방에 도달하면 여정이 끝나므로 번 방의 목록은 입력에 없다.
두 줄 중 첫 줄에는 목표 방의 개수 이 주어진다. () 둘째 줄에는 목표 방 개가 주어지며, 이면 이 줄은 빈 줄이다. 각 목록은 이상 이하의 정수로 이루어지고 엄격히 증가하는 순서로 정렬되어 있다. 따라서 한 목록에 같은 방이 두 번 나오지 않는다.
모든 목록의 목표 방 개수를 합한 값은 을 넘지 않는다.
출력
한 줄에 두 단어를 공백으로 구분해 출력한다.
- 죄인이 무작위로 이동해 왕좌의 방에 도달할 확률이 100%이면 첫 단어는
PARDON, 그렇지 않으면PRISON이다. - 전송 횟수의 상한이 존재하면 둘째 단어는
LIMITED, 존재하지 않으면UNLIMITED이다.