Locks and Keys

The wizard Jaehwan is trapped in a maze of $V$ rooms and $V-1$ doors. Each door connects two rooms in both directions, and it is always possible to travel from any room to any other room (so the maze is a tree). There are $C$ locks in $C$ distinct colors and $C$ keys in the same $C$ colors. Each door may be locked by at most one lock, and each room may hold at most one key; every color has exactly one lock and exactly one key.

Jaehwan is a wizard and could normally open locks by magic, but he left his spellbook behind, so right now he cannot use magic at all.

He is currently in room $X$ and wants to reach room $Y$, where the spellbook is. In one step he can move from his current room to an adjacent room through a door. If a door is locked, he can open it and pass only while holding a key of the same color as the lock. Once a door has been opened it stays open, so he may pass through it freely afterwards.

Jaehwan can hold only one key at a time. He may not set a key down in another room to reuse it later, and opening a locked door consumes the key (it disappears).

Given the structure of the maze and the positions of the $C$ keys and $C$ locks, determine whether Jaehwan can travel from room $X$ to room $Y$.

The input consists of several test cases.

The first line of each test case contains four integers $V$, $C$, $X$, and $Y$: the number of rooms $V$ ($1 \le V \le 1500$), the number of locks (and keys) $C$ ($0 \le C < V$), and the numbers of the start room $X$ and the destination room $Y$. Rooms are numbered from $0$ to $V-1$.

The next $C$ numbers give, in increasing order of color (color $0$ through color $C-1$), the room that holds the key of that color.

The following $V-1$ lines each describe a door as $A$ $B$ $L$. If $0 \le L < C$, the door between rooms $A$ and $B$ is locked by the lock of color $L$; if $L = -1$, the door is not locked.

The last line of the input is 0 0 0 0.

For each test case, print a single line: Possible if Jaehwan can travel from room $X$ to room $Y$, and Impossible otherwise.