A16846 | 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$ 的分配。