CF2206C Upside Down Dijkstra

你的弟弟手中有一个包含 $n$ 个点、$m$ 条边的连通无向图。顶点编号为 $1$ 到 $n$，边编号为 $1$ 到 $m$。第 $j$ 条边连接 $u_j$ 和 $v_j$，边权为正整数 $w_j$。 你的弟弟实现了 Dijkstra 算法，以查找从顶点 $1$ 到所有其他顶点的最短距离。伪代码如下。数组 $S$ 记录了每个顶点首次从堆中弹出的顺序。注意，虽然同一个顶点的元组可能被多次压入堆，但每个顶点恰好只会被加入 $S$ 一次。 然而，你的弟弟犯了个致命错误。在代码中，堆始终弹出最大元组而不是最小元组。堆在排序元组 $(\mathit{dist}, u)$ 时，以 $\mathit{dist}$（距离）较大为优先级，若距离相同则 $u$ 较大优先。  你的弟弟告知你图的结构，也就是所有的 $u_j$ 和 $v_j$ 对（$1 \le j \le m$），但没有告知边权 $w_j$。他只把数组 $S = (s_1, s_2, \ldots, s_n)$ 告诉了你，希望你根据这些信息重建出边权。你的任务是，找到一组整数 $w_1, w_2, \ldots, w_m$（$1 \leq w_j \leq 10^9$，对于所有 $j$），使得运行你弟弟的错误代码时得到的数组正好为 $S$。 如果不存在这样的边权分配，请输出 impossible。否则，输出任意一组合法的边权分配。

第一行输入两个整数 $n$ 和 $m$（$2 \leq n \leq 100\,000$；$n-1 \leq m \leq 200\,000$）。 接下来 $m$ 行，每行两个整数 $u_j$ 和 $v_j$（$1 \leq u_j < v_j \leq n$；对于所有 $j \neq k$，$(u_j, v_j) \neq (u_k, v_k)$）。保证图是连通的。 最后一行输入 $n$ 个整数 $s_1, s_2, \ldots, s_n$（$1 \leq s_i \leq n$；对于所有 $i \neq \ell$，$s_i \neq s_\ell$）。

如果不存在与给定 $S$ 相符的边权分配，输出 impossible。 否则，输出一行 $m$ 个整数 $w_1, w_2, \ldots, w_m$，为每条边分配的权值，满足 $1 \leq w_j \leq 10^9$，并且你弟弟错误代码运行时得到的数组正好为 $S$。 如果有多组输出，任意一组均可。 可以证明，如果有任何实现 $S$ 的正整数边权分配，则必然存在一组满足 $1 \le w_j \le 10^9$ 的分配。

样例输入输出 #1 说明 下图展示了样例输出中分配的边权与图结构。 图 C.1：分配了边权的图。这样分配后，你弟弟的错误代码运行流程如下： 1. 初始时，堆为 $\{(0, 1)\}$。 2. 弹出 $(0, 1)$，顶点 $1$ 首次弹出。接下来堆里有 $\{(3, 4),(3, 2),(2, 5)\}$。 3. 弹出 $(3, 4)$，顶点 $4$ 被弹出。堆变为 $\{(9, 3),(6, 1),(5, 5),(3, 2),(2, 5)\}$。 4. 弹出 $(9, 3)$，顶点 $3$ 被弹出。堆变为 $\{(15, 4),(10, 5),(10, 2),(6, 1),(5, 5),(3, 2),(2, 5)\}$。 5. 弹出 $(10, 5)$，顶点 $5$ 被弹出。堆变为 $\{(12, 4),(12, 1),(11, 3),(10, 2),(6, 1),(5, 5),(3, 2),(2, 5)\}$。 6. 弹出 $(10, 2)$，顶点 $2$ 被弹出。 结果 $S = (1,4,3,5,2)$。 由 ChatGPT 5 翻译