Hogwarts
시간 제한1초메모리 제한512 MB
꼭짓점 n개와 각 방마다 4개의 간선 레이블이 있는 두 그래프가 주어질 때, 옛 그래프에서 1번 방에서 n번 방으로 가는 모든 명령 수열이 새 그래프에서도 1번 방에서 n번 방으로 가는지 판정한다.
문제
Hogwarts School of Witchcraft and Wizardry는 학기 중 많은 학생이 생활하는 곳이다. 이 학교에는 복도와 계단으로 연결된 여러 방이 있다. 각 방에는 1, 2, 3, 4의 네 가지 출구가 있다. 어떤 출구는 다른 방으로 이어지고, 어떤 출구는 막혀 있으며, 어떤 출구는 방금 나온 방으로 되돌아가기도 한다.
신입생들은 길을 찾기 어려워하는데, 특히 복도와 계단이 수시로 움직여 방들을 서로 끊거나 다시 연결하기 때문이다! 다행히 이런 재배치는 아무도 학교를 걷고 있지 않을 때만 일어난다. 당신이 알고 싶은 것은 입구에서 기숙사까지 가는 방법뿐이다. 선배가 1, 2, 3, 4로 이루어진 수열을 지시로 주었다. 수열의 첫 번째 수는 시작 방에서 나가야 할 출구이다. 두 번째 수는 경로의 두 번째 방에서 나가야 할 출구이고, 이런 식으로 이어진다. 어느 지점에서든 지시된 출구가 막혀 있으면, 입구로 돌아가고 포기한다. 성공하려면 전체 수열을 모두 따른 끝에 기숙사에 도착해야 한다. 전체 수열을 따르기 전에 기숙사에 도착한 것처럼 보여도 그것이 환영인지 확신할 수 없다. 따라서 전체 수열을 따른다.
당신은 지시를 주의 깊게 따라 기숙사에 도착했다. 하지만 선배가 지시를 준 뒤 방들이 서로 연결된 방식이 바뀌었고, 도중에 지나온 방이 완전히 달라도 우연히 같은 목적지에 도착했을 뿐이다.
당신은 자신이 운이 좋았을 뿐인지, 아니면 복도와 계단의 재배치가 지시를 따라도 여전히 같은 목적지에 이르도록 보장하는지 궁금하다. 마법 같지 않은가?
선배가 입구에서 기숙사까지 걸었을 때의 학교 배치와, 당신이 주어진 지시를 따르기 시작할 때의 학교 배치가 주어진다. 선배를 입구에서 기숙사까지 이끈 모든 가능한 지시 수열이, 당신이 걷는 배치에서도 당신을 기숙사로 이끄는지 알고 싶다. 선배와 당신 모두 학교 입구에서 걷기 시작한다.
입력
첫 번째 줄에는 학교의 방 수를 나타내는 정수 n (2 ≤ n ≤ 1 000)이 주어진다. 방은 1부터 n까지 번호가 매겨져 있으며, 방 1은 입구이고 방 n은 기숙사이다.
다음 n개의 줄은 선배가 기숙사까지 걸었을 때의 학교 배치를 설명하고, 그다음 n개의 줄은 당신이 기숙사로 걷기 시작할 때의 학교 배치를 설명한다.
학교 배치의 i번째 줄은 출구 1, 2, 3, 4가 각각 어느 방으로 이어지는지를 나타내는 네 개의 음이 아닌 정수로 이루어진다. 방 번호가 0이면 해당 출구는 막혀 있다.
출력
선배가 입구에서 기숙사까지 걸어가는 것이 불가능하면 Impossible을 출력한다.
가능하면, 선배를 입구에서 기숙사까지 이끄는 모든 지시 수열을 따라 당신이 입구에서 기숙사까지 갈 수 있을 때 Yes를 출력한다. 그렇지 않으면 No를 출력한다.