SP10089 LOCKKEY - Locks and Keys

A wizard is in a labyrinth where there are _V_ rooms and _V_−1 doors connecting some pairs of rooms in both directions, in such a way that there is always a sequence of doors one can traverse to go from a room to any other room. Additionally, there are _C_ locks and _C_ keys of _C_ different colours (one of each) in some of the doors and rooms of the maze, respectively; each door has at most one lock, and there is at most one key placed in each room. It should be an easy matter for the wizard to bypass the lock system, were it not for the fact that he forgot his spell book, without which his wizardry is utterly useless. The wizard is currently in room _X_, and he wants to get his spell book, located in room _Y_, without taking too long. At every step he may go to an adjacent room through one of the doors. Of course, if the door is locked, he needs to be carrying the key of the same colour as the lock (unless, of course, that door has already been unlocked). The wizard can carry only one key at a time and after picking up a key it is not possible for him to drop it somewhere in the maze in order to take it again afterwards. Once a door has been unlocked, the key is thrown away since it is no longer any use. Given the maze and the positions of the _C_ keys and _C_ locks, determine how to reach _Y_ from _X_, if possible. Any path whose length does not exceed 4 · (_C_ + 1) · _V_ is acceptable. **Input** The first line of each case contains four integers: the number _V_ of rooms in the maze (1 V C of locks (0 C < _V_), and rooms _X_ and _Y_ numbered 0,1,…,_V_−1. Then comes a (possibly empty) line with _C_ integers indicating the location of each of the keys, in order of increasing colour. The next _V_ − 1 lines describe the maze: each contains three integers _A_ _B_ _L_, meaning that there is a door between rooms _A_ and _B_ which can be unlocked with the key of colour _L_, if 0 L < _C_; a value of −1 for _L_ indicates that no lock is needed. The last line has _V_, _C_, _X_, _Y_ = 0, 0, 0, 0. **Output** There is one line of output per test case. If there is no solution, output Impossible. Otherwise print the full path corresponding to your solution in the format _L_: _V_ $ _{0} $ … _V_ $ _{L} $ , where _L_ C + 1) _V_ is the length of a path from _X_ to _Y_, and _X_ = _V_ $ _{0} $ , _V_ $ _{1} $ , …, _V_ $ _{L−1} $ , _V_ $ _{L} $ = _Y_ is the sequence of _L_ + 1 vertices visited in the right order. A single space must precede each vertex in the path; see sample output for clarification. **Sample Input** ```

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
```
                            

N/A

N/A