P15152 [SWERC 2024] Yaxchilán Maze

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. 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?

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

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).

### 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. ### Limits - $1 \leq A \leq 50$; - $2 \leq N \leq 50000$; - $1 \leq M \leq 100000$; - $1 \leq E \leq 100$; - $A + E \leq N$ (no chamber is both a starting chamber and an exit chamber); - $1 \leq T \leq 500000$; - $0 \leq B \leq N$; - $0 \leq b_i < N$ for $i = 0, \ldots, B-1$; - The $b_i$'s are unique; - $0 \leq K < N$; - $0 \leq u_t < N$ for $t = 0, \ldots, T-1$; - $0 \leq v_t < N$ for $t = 0, \ldots, T-1$;