SP10089 LOCKKEY - Locks and Keys

一位巫师迷失在一个复杂的迷宫中，这个迷宫由 $V$ 个房间和 $V-1$ 扇连接不同房间的门组成，每扇门都可以双向通行，使得从任意一个房间可以到达其他所有房间。此外，迷宫里还放置了 $C$ 把不同颜色的锁和对应颜色的钥匙，钥匙和锁分别放在某些房间和门上。每扇门最多只能挂一把锁，每个房间最多只放置一把钥匙。如果巫师还记得他的魔法书，化解这些锁将是轻而易举。但遗憾的是，他忘记带魔法书，现在他的法力全都无从施展。目前，巫师正待在房间 $X$，他需要尽快到达房间 $Y$ 找回他的魔法书。巫师每一步只能穿过一扇通向相邻房间的门。如果一扇门上锁了，他需要拿着和锁同色的钥匙才能通过（当然，如果门已解锁，则无需钥匙）。巫师每次只能携带一把钥匙，并且一旦拿取钥匙就无法放下或再拿起。门一旦被解锁，钥匙便会被丢弃，因为不再需要。 给定迷宫内的钥匙和锁的位置，判断巫师能否从 $X$ 到达 $Y$。任何路径长度不超过 $4 \cdot (C + 1) \cdot V$ 的解都被接受。

每组测试数据的第一行包括四个整数：迷宫中的房间数 $V$、锁的数量 $C$、起始房间编号 $X$ 和目标房间编号 $Y$（编号从 $0$ 到 $V-1$）。接下来的一个可能为空的行列出 $C$ 个整数，表示每把钥匙所在房间的位置，按颜色升序排列。接下来的 $V-1$ 行描述迷宫的连接结构：每行包含三个整数 $A$、$B$ 和 $L$，表示房间 $A$ 和 $B$ 之间有一扇门，若 $0 \leq L < C$，则这扇门上锁且需对应颜色 $L$ 的钥匙解锁；若 $L = -1$，则表示这扇门没有锁。 最后一行输入为 $0, 0, 0, 0$，表示输入结束。

对于每组测试数据，输出结果一行。如果无法找到从 $X$ 到 $Y$ 的路径，输出 `Impossible`。否则，输出路径，格式为 `L: V_0 ... V_L`，其中 $L$ 是路径长度（满足 $L \leq 4 \cdot (C + 1) \cdot V$），路径顺序为 $V_0 = X, V_1, ..., V_L = Y`。注意每个顶点间用空格隔开。

- $1 \leq V \leq 10^5$ - $0 \leq C < V$ **本翻译由 AI 自动生成**