LOCKKEY - Locks and Keys

no tags 

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 ≤ 1 500), the number 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 LV0VL, where L ≤ 4 (C + 1) V is the length of a path from X to Y, and X = V0, V1, …, VL−1, VL = 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



Sample Output

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

Problemsetter: Javier Gómez Serrano

hide comments
David García Soriano: 2013-05-12 12:15:33

@Jacob Plachta
Thanks for letting us know, the previous validator might have accepted some incorrect submissions, so we have rejudged them.

On the other hand note that the opposite is not possible, i.e., all submissions that were marked incorrect are indeed incorrect (including yours). The validator tells you what went wrong. Also, please keep the discussion civil. That typo is the only issue with an otherwise perfectly fine validator, and no contest was affected by it, let alone 'ruined'.

Last edit: 2013-05-12 12:54:17
Jacob Plachta: 2013-04-08 22:34:26

This problem has quite the fantastic validator... it's blatantly incorrect (in at least one way).

After struggling with a solution which I'm quite sure was correct not getting AC, I downloaded the official SWERC validator, and discovered a fantastic bit of coding:

"check(!((i == 0 && v[i] != src) || (i == len - 1 && v[i] == dest)), "incorrect path endpoint");"

Here, it attempts to check if the path starts at X and ends at Y. However, the latter half is completely wrong - it is instead checking if the 2nd-last room is not Y. This line should instead read as follows:

"check(!((i == 0 && v[i] != src) || (i == len && v[i] != dest)), "incorrect path endpoint");"

To confirm, I then submitted a solution which correctly checks if any path is possible - but, if so, always outputs a dummy path of length 0 ("0: X"). This solution was accepted.

Though I always find it quite exhilarating to identify issues with official contest problems, this should probably be fixed :) I can only hope that the SWERC 2010 contest wasn't too ruined by this error...

Last edit: 2013-04-08 23:57:54
(test): 2012-05-04 15:58:52

Be careful, this one treats whitespaces seriously. If you print one more space at the end, you will get WA.

suhang: 2012-04-15 03:15:02

@David García Soriano
Can you help me?

suhang: 2012-04-09 02:47:58

I pass on my pc,why wa?= =|||
@David García Soriano
can you give me some test?
I pass by specil judge on my pc!

Last edit: 2012-04-14 02:07:56

Added by:David García Soriano
Date:2011-11-24
Time limit:1.309s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Soutwestern Europe Regional, SWERC 2010