P1023

Locks and keys

Locks and keys

一座迷宫由 VV 个房间和 V−1V-1 扇双向门组成，每扇门连接两个房间，并且任意两个房间之间都可以通过若干扇门互相到达。

迷宫中共有 CC 种颜色的锁和钥匙。每种颜色恰好对应一把锁和一把钥匙。每扇门至多安装一把锁，每个房间至多放置一把钥匙。钥匙只能打开颜色相同的锁。

巫师最初位于房间 XX，他的咒语书位于房间 YY。每一步，巫师可以通过一扇门进入相邻房间。如果门被锁住，巫师必须携带颜色相同的钥匙才能通过；已经被打开的门可以直接通过。

巫师一次只能携带一把钥匙。拿起钥匙后，他不能将其丢弃在迷宫中并在之后重新拾取。使用钥匙打开对应的锁后，该钥匙会被丢弃，而这扇门将永久保持打开状态。

请判断巫师能否从房间 XX 到达房间 YY。如果可以，请给出一种行走方案。任何步数不超过 4(C+1)V4(C+1)V 的合法方案均可接受。

输入格式

输入包含多组测试数据。

每组测试数据的第一行包含四个整数 VV、CC、XX 和 YY，分别表示房间数量、锁与钥匙的颜色数量、巫师的起始房间和咒语书所在的房间。房间编号为 0,1,…,V−10,1,\ldots,V-1。

第二行包含 CC 个整数，依次表示颜色为 0,1,…,C−10,1,\ldots,C-1 的钥匙所在的房间。当 C=0C=0 时，该行为空。

接下来 V−1V-1 行描述迷宫中的门。每行包含三个整数 AA、BB 和 LL，表示房间 AA 与房间 BB 之间有一扇双向门：

  • 若 0≤L<C0\le L<C，则门上安装了颜色为 LL 的锁；
  • 若 L=−1L=-1，则该门没有锁。

当读入 V=C=X=Y=0V=C=X=Y=0 时，输入结束，该行不属于任何一组测试数据。

输出格式

对于每组测试数据，输出一行。

如果不存在合法方案，输出 Impossible。

否则，按照 L: V0 ... VL 的格式输出方案，其中 LL 表示总步数，并且应满足 L≤4(C+1)VL\le 4(C+1)V；V0,V1,…,VLV_0,V_1,\ldots,V_L 表示巫师依次经过的房间，要求 V0=XV_0=X、VL=YV_L=Y，且序列中相邻的两个房间之间存在一扇门。

冒号后以及相邻房间编号之间均使用一个空格分隔。

样例输入

1 0 0 0

3 1 0 2
1
0 1 -1
0 2 0

3 2 0 2
1 2
0 1 1
0 2 0

5 3 0 4
2 0 3
0 1 0
0 2 -1
1 3 1
2 4 2

0 0 0 0

样例输出

0: 0
3: 0 1 0 2
Impossible
10: 0 2 0 1 0 1 3 1 0 2 4

数据范围

  • 1≤V≤15001\le V\le 1500；
  • 0≤C<V0\le C<V；
  • 0≤X,Y<V0\le X,Y<V；
  • 对于每扇门，L=−1L=-1 或 0≤L<C0\le L<C；
  • 合法输出方案的步数须满足 L≤4(C+1)VL\le 4(C+1)V。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

1 0 0 0

3 1 0 2
1
0 1 -1
0 2 0

3 2 0 2
1 2
0 1 1
0 2 0

5 3 0 4
2 0 3
0 1 0
0 2 -1
1 3 1
2 4 2

0 0 0 0

输出

0: 0
3: 0 1 0 2
Impossible
10: 0 2 0 1 0 1 3 1 0 2 4