F. Yaxchilán Maze
time limit per test
5 seconds
memory limit per test
2048 MB
input
standard input
output
standard output

Years spent deciphering Mayan glyphs had led Dr Wood, a famous archeologist, to this very moment: inside a chamber of the Yaxchilán maze, in the middle of the Lacandon Jungle, the last undiscovered Mayan codex appeared before her. It was beautiful, protected by jaguar pelt and adorned with jade. However, as soon as she touched it, all the corridors of the maze closed. She was now a prisoner of the maze. Worse, she was not alone, but had a full team of archeologists with her that were also held prisoner in different chambers of the maze.

As she examined the codex, a series of intricate diagrams caught her eye. They depicted the maze, its corridors morphing into different configurations, each aligned with a specific position of the sun. Another set of diagrams showed intricately carved holes in the walls together with a chilling depiction of a giant wasp. A realization dawned on her – the Maya had designed this maze to change with the sun's position, and some chambers were booby-trapped with a giant nest of deadly wasps.

Namely, there are $$$N$$$ chambers in the maze numbered $$$0, \ldots, N-1$$$. Dr Wood and the members of her team start in chambers $$$0, 1, \ldots, A - 1$$$ (one person per chamber). There are $$$E$$$ exits: chambers $$$N - E, \ldots, N - 1$$$. Initially, the maze contains no open corridors. At each hour (00:00, 01:00, 02:00 and so on, represented by integers 0, 1, 2 and so on), a new corridor between two chambers opens. This corridor stays open for exactly $$$M$$$ hours minus one minute. Corridors are bi-directional.

Among the $$$N$$$ chambers, $$$B$$$ are booby-trapped. The trap of a chamber triggers as soon as it is connected to at least $$$K$$$ other chambers. When triggered, a gigantic swarm of deadly wasps appears in the chamber and immediately spreads to all chambers connected to the booby-trapped chamber. Furthermore, as time progresses, the wasps never disappear from a chamber, and worse, they continue to spread instantaneously from chambers that contain wasps to newly connected chambers. Two chambers are considered connected at a given time when there exists a path of one or multiple open corridors that allows going from one chamber to the other.

Thanks to the codex and to her knowledge of the maze (and smartphones!), Dr Wood and each member of her team have full information on the maze at hour 0, including all future events: in particular, they each know where they are in the maze, where corridors lead to, the exact time, when corridors open and close and which chambers they connect, the location of the booby-traps, exits, $$$K$$$, and can deduce which chambers are or will be filled with deadly wasps. All the archeologists can move freely and independently from each other using the open corridors at all times. They run fast and can move to any reachable chamber in less than 59 minutes. If an archeologist ends up in a chamber filled with deadly wasps, he or she dies and cannot exit the maze.

The exit chambers behave as the other chambers: they can be filled with wasps and be booby-trapped.

As soon as an archeologist reaches any exit chamber not filled with wasps, she or he exits the maze and its dangers. Can you tell the earliest time when each archeologist can exit the maze?

Input
  • The first line contains the integer $$$A$$$, the number of archeologists.
  • The second line contains the integer $$$N$$$.
  • The third line contains the integer $$$M$$$.
  • The fourth line contains the integer $$$E$$$.
  • The fifth line contains the integer $$$T$$$, the number of hours at which corridors open.
  • The sixth line contains $$$B$$$, followed by the list of the $$$B$$$ space-separated booby-trapped chambers $$$b_i$$$.
  • The seventh line contains $$$K$$$.
  • In the next $$$T$$$ lines, line $$$t$$$ contains two space-separated integers $$$u_t, v_t$$$ representing a corridor that opens at hour $$$t$$$ and connects chambers $$$u_t$$$ and $$$v_t$$$. $$$t$$$ goes from $$$0$$$ to $$$T - 1$$$ (inclusive). Multiple corridors can connect the same two chambers. A corridor can connect a chamber to itself.
Output

The output should contain $$$A$$$ lines. The $$$i$$$-th line represents the $$$i$$$-th archeologist. If the $$$i$$$-th archeologist can exit the maze, it should be the integer representing the earliest hour at which she or he can exit. Otherwise, it should be "IMPOSSIBLE" (without quotes).

Limits

  • $$$1 \leqslant A \leqslant 50$$$;
  • $$$2 \leqslant N \leqslant 50\,000$$$;
  • $$$1 \leqslant M \leqslant 100\,000$$$;
  • $$$1 \leqslant E \leqslant 100$$$;
  • $$$A + E \leqslant N$$$ (no chamber is both a starting chamber and an exit chamber);
  • $$$1 \leqslant T \leqslant 500\,000$$$;
  • $$$0 \leqslant B \leqslant N$$$;
  • $$$0 \leqslant b_i \lt N$$$ for $$$i=0,\dots, B-1$$$;
  • The $$$b_i$$$'s are unique;
  • $$$0 \leqslant K \lt N$$$;
  • $$$0 \leqslant u_t \lt N$$$ for $$$t=0,\dots, T-1$$$;
  • $$$0 \leqslant v_t \lt N$$$ for $$$t=0,\dots, T-1$$$;
Examples
Input
1
5
1
1
5
0
0
0 1
0 2
2 3
2 4
0 4
Output
3
Input
1
4
1
1
3
0
0
0 1
2 3
1 2
Output
IMPOSSIBLE
Input
4
10
2
2
11
2 3 7
2
0 1
1 2
2 3
1 4
4 9
5 6
0 6
5 7
1 6
7 8
6 8
Output
9
9
9
IMPOSSIBLE
Note

Sample Explanation 1

There are no booby-traps. Dr Wood (the only archeologist) starts at $$$0$$$ and the exit is $$$4$$$. After the corridor 0 2 opens, she goes from chamber $$$0$$$ to chamber $$$2$$$. She stays there until the corridor 2 4 opens, which allows her to reach chamber $$$4$$$ and exit at hour $$$3$$$.

Sample Explanation 2

There are no booby-traps. Dr Wood (the only archeologist) starts at $$$0$$$ and the exit is $$$3$$$. Unfortunately, Dr Wood can only reach chamber $$$2$$$ after the corridor 2 3 leading to the exit closed. She cannot exit the maze.

Sample Explanation 3

The fastest path to an exit for the first archeologist starting at 0 is to go to chamber 5 at hour $$$6$$$ using corridors 0 6 and 5 6, then to chamber 7 at hour $$$7$$$ using the corridor 5 7, and finally reach chamber 8 (an exit) at hour 9 using the corridor 7 8. Note that chamber 7 is booby-trapped, but the wasps only appear at hour 10, after the first archeologist exited the maze.

The second archeologist starting at 1 can move to chamber 0 at hour 0 and then follow the path of the first archeologist.

The third archeologist starting at 2 can move to chamber 0 at hour 1 and then follow the first two archeologists.

The last archeologist starting at 3 is killed by the wasps at hour 2.

At the end, chambers 1, 2, 3, 4, 6, 7, 8, 9 are filled with wasps.