자물쇠와 열쇠

마법사 이재환은 V개의 방과 V-1개의 문으로 이루어진 미로에 갇혀있다. 문은 방을 양방향으로 연결하고 있고, 한 방에서 다른 방으로 가는 경로는 항상 존재한다. 또, C개의 서로 다른 색상으로 이루어진 C개의 자물쇠와 C개의 열쇠가 있다. 문은 최대 한 개의 자물쇠로 잠겨있을 수 있고, 방에는 최대 한 개의 열쇠가 놓여져 있다.

재환이는 마법사이기 때문에, 자물쇠를 마법으로 풀면 된다. 하지만, 주문책을 놓고 왔기 때문에, 마법을 전혀 할 수 없다. 

재환이는 현재 방 X에 있고, 방 Y에 있는 주문북을 찾으러 가려고 한다. 재환이는 현재 있는 방과 인접한 방으로 문을 통해 한 번에 이동할 수 있다. 문이 잠겨있는 경우에는 자물쇠의 색상과 같은 색상의 열쇠가 있어야 문을 열 수 있다.

재환이는 한 번에 열쇠 하나만 들고 있을 수 있다. 또, 열쇠를 집은 이후에 나중에 다시 사용하기 위해서 열쇠를 다른 방에 내려 놓을 수 없다. 자물쇠로 잠겨있는 문을 열게 되면, 열쇠는 사라지게 된다.

미로와 열쇠 C개와 자물쇠 C개의 위치가 주어진다. 이때, X에서 Y로 이동하는 것이 가능한지 알아내는 프로그램을 작성하시오. 경로의 길이는 4·(C+1)·V를 넘을 수 없다.

입력은 여러 개의 테스트 케이스로 이루어져 있다.

첫째 줄에는 네 정수가 주어진다. 방의 개수 V (1 ≤ V ≤ 1500), 자물쇠의 수 (0 ≤ C < V), 방 번호 X와 Y가 주어진다. 방 번호는 0번부터 V-1가지 번호가 매겨져 있다. 다음 C개 줄에는 색의 번호가 증가하는 순서대로 키가 들어있는 방의 번호가 주어진다. 그 다음 V-1개 줄에는 미로의 정보 A B L이 주어진다. 0 ≤ L < C인 경우에는 방 A와 B를 연결하는 문을 잠구는 자물쇠의 색은 L이라는 뜻이고, -1인 경우에는 잠겨있지 않다는 뜻이다.

입력의 마지막 줄은 V,C,X,Y = 0,0,0,0 이다.

각 테스트 케이스마다 한 줄씩 출력한다. 답이 없는 경우에는 Impossible을 출력한다. 그렇지 않으면 L: V0 ... VL 형식으로 경로를 출력한다. L ≤ 4(C+1)V 은 X에서 Y로 가는 경로이고, X=V0,V1,...,VL-1,VL = Y는 X에서 Y로 가기 위해 지나가야 하는 방의 번호 L+1개이다. 각 정점을 출력하기 전에 공백을 하나 출력해야 한다.