P15152 [SWERC 2024] Yaxchilán Maze

伍德博士（Dr Wood）花费数年破译玛雅象形文字，终于迎来了这一时刻：在 Lacandon 丛林深处的 Yaxchilán 迷宫的一个密室中，最后一部未被发现的玛雅手抄本出现在她面前。它美丽非凡，用美洲豹皮保护并装饰着玉石。然而，当她触碰它时，迷宫的所有走廊都关闭了。她现在成了迷宫的囚徒。更糟的是，她并非独自一人，而是带着一整支考古队，他们也被困在迷宫的不同密室中。 当她检查手抄本时，一系列复杂的图表引起了她的注意。这些图表描绘了迷宫，其走廊随着太阳的特定位置而变化成不同的构型。另一组图表展示了墙上精心雕刻的孔洞，以及一幅令人毛骨悚然的巨型黄蜂图案。她恍然大悟——玛雅人设计了这个随太阳位置变化的迷宫，并且一些密室设有致命黄蜂巨巢的陷阱。 具体来说，迷宫中有 $N$ 个密室，编号为 $0, \ldots, N-1$。伍德博士和她的团队成员开始时分别位于密室 $0, 1, \ldots, A-1$（每人一个密室）。有 $E$ 个出口：密室 $N-E, \ldots, N-1$。最初，迷宫中没有任何开放的走廊。在每个小时（00:00, 01:00, 02:00 等，用整数 $0, 1, 2$ 等表示），两个密室之间会有一条新的走廊开放。这条走廊会保持开放恰好 $M$ 小时减去一分钟。走廊是双向的。 在这 $N$ 个密室中，有 $B$ 个设有陷阱。一旦一个密室连接到至少 $K$ 个其他密室，该密室的陷阱就会触发。触发时，一大群致命黄蜂会出现在该密室，并立即蔓延到所有与设有陷阱的密室相连的密室。此外，随着时间的推移，黄蜂永远不会从密室中消失，更糟的是，它们会继续从已有黄蜂的密室瞬间蔓延到新连接的密室。在给定时间，如果存在一条或多条开放走廊的路径允许从一个密室走到另一个密室，则认为这两个密室是连通的。所有考古学家始终可以自由且独立地使用开放走廊移动。他们跑得很快，可以在不到 59 分钟内移动到任何可达的密室。如果一位考古学家最终进入充满致命黄蜂的密室，他或她就会死亡，无法离开迷宫。 出口密室的行为与其他密室相同：它们也可能充满黄蜂并设有陷阱。 一旦一位考古学家到达任何没有黄蜂的出口密室，他或她就会离开迷宫及其危险。你能告诉每位考古学家能够离开迷宫的最早时间吗？

- 第一行包含整数 $A$，表示考古学家的数量。 - 第二行包含整数 $N$。 - 第三行包含整数 $M$。 - 第四行包含整数 $E$。 - 第五行包含整数 $T$，表示走廊开放的小时数。 - 第六行包含 $B$，后跟 $B$ 个空格分隔的设有陷阱的密室 $b_i$。 - 第七行包含 $K$。 - 接下来的 $T$ 行中，第 $t$ 行包含两个空格分隔的整数 $u_t, v_t$，表示在小时 $t$ 开放并连接密室 $u_t$ 和 $v_t$ 的走廊。$t$ 从 $0$ 到 $T-1$（含）。多条走廊可以连接相同的两个密室。一条走廊可以连接一个密室到它自身。

输出应包含 $A$ 行。第 $i$ 行代表第 $i$ 位考古学家。如果第 $i$ 位考古学家可以离开迷宫，则输出一个整数表示他或她可以离开的最早小时。否则，输出 "IMPOSSIBLE"（不带引号）。

#### 样例解释 1 没有陷阱。伍德博士（唯一的考古学家）从 $0$ 开始，出口是 $4$。在走廊 $0$ $2$ 开放后，她从密室 $0$ 移动到密室 $2$。她待在那里直到走廊 $2$ $4$ 开放，这使她能在小时 $3$ 到达密室 $4$ 并离开。 #### 样例解释 2 没有陷阱。伍德博士（唯一的考古学家）从 $0$ 开始，出口是 $3$。不幸的是，伍德博士只能在走廊 $2$ $3$ 关闭后才能到达密室 $2$，而该走廊通向出口。她无法离开迷宫。 #### 样例解释 3 从 $0$ 开始的第一位考古学家到达出口的最快路径是：在小时 $6$ 使用走廊 $0$ $6$ 和 $5$ $6$ 到达密室 $5$，然后在小时 $7$ 使用走廊 $5$ $7$ 到达密室 $7$，最后在小时 $9$ 使用走廊 $7$ $8$ 到达密室 $8$（一个出口）。注意密室 $7$ 设有陷阱，但黄蜂只在小时 $10$ 出现，即第一位考古学家离开迷宫之后。 从 $1$ 开始的第二位考古学家可以在小时 $0$ 移动到密室 $0$，然后跟随第一位考古学家的路径。 从 $2$ 开始的第三位考古学家可以在小时 $1$ 移动到密室 $0$，然后跟随前两位考古学家。 从 $3$ 开始的最后一位考古学家在小时 $2$ 被黄蜂杀死。 最终，密室 $1, 2, 3, 4, 6, 7, 8, 9$ 充满了黄蜂。 #### 数据范围 - $1 \leq A \leq 50$； - $2 \leq N \leq 50000$； - $1 \leq M \leq 100000$； - $1 \leq E \leq 100$； - $A + E \leq N$（没有密室既是起始密室又是出口密室）； - $1 \leq T \leq 500000$； - $0 \leq B \leq N$； - $0 \leq b_i < N$，其中 $i = 0, \ldots, B-1$； - $b_i$ 互不相同； - $0 \leq K < N$； - $0 \leq u_t < N$，其中 $t = 0, \ldots, T-1$； - $0 \leq v_t < N$，其中 $t = 0, \ldots, T-1$。 翻译由 DeepSeek 完成