Locks and keys#1827
A wizard is in a labyrinth with rooms and V-1 doors. Each door connects two rooms in both directions. It is always possible to go from any room to any other room by going through a sequence of doors. There are locks and keys of different colors (each key has its own color); each door may have at most one lock, and each room may contain at most one key. Normally, it would not be difficult for the wizard to deal with the lock system, but he has forgotten his spell book, so he cannot use his magic. Currently, the wizard is in room , and his spell book is in room . He wants to reach the book as quickly as possible. At each step, the wizard can move to an adjacent room through a door. If a door is locked, the wizard must carry the key of the same color as the lock (unless the door has already been unlocked). The wizard can only carry one key at a time. After picking up a key, he cannot drop it anywhere in the labyrinth to pick it up again. Once a door is unlocked, the key is discarded, since it is no longer needed.
Given the labyrinth and the positions of the keys and locks, determine a way to get from to , if possible. Any path whose length does not exceed 4(C+1)V is acceptable.
The first line of each test case contains four integers: the number of rooms in the labyrinth (1 \leq V \leq 1500), the number of locks (0 \leq C < V), and the room numbers and . Rooms are numbered 0, 1, \dots, V-1. Then comes a (possibly empty) line with integers describing the location of each key, in order of increasing color. The next V-1 lines describe the labyrinth: each contains three integers , , , meaning that there is a door between rooms and that can be unlocked with the key of color if 0 \leq L < C. A value of for means the door is not locked.
The last line contains V, C, X, Y = 0, 0, 0, 0 and should not be processed.
Output one line per test case. If there is no solution, print Impossible. Otherwise, print the full path in the format : V_0, \dots, V_L, where L \leq 4(C+1)V is the length of a path from to , and X = V_0, V_1, \dots, V_{L-1}, V_L = Y is the sequence of L+1 vertices visited in order. Each vertex in the output path must be preceded by a space.
Example 1