你的小兄弟有一个由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成的无向连通图。顶点编号从 $$$1$$$ 到 $$$n$$$,边编号从 $$$1$$$ 到 $$$m$$$。边 $$$j$$$ 用 a 连接顶点 $$$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$$$。
找到任何此类边权重分配。如果不存在这样的分配,则报告这是不可能的。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 100\,000$$$; $$$n-1 \leq m \leq 200\,000$$$)。
接下来的 $$$m$$$ 行的第 $$$j$$$ 包含两个整数 $$$u_j$$$ 和 $$$v_j$$$ ($$$1 \leq u_j \lt v_j \leq n$$$; $$$(u_j, v_j) \neq (u_k, v_k)$$$ 对于所有 $$$j \neq k$$$)。输入保证图是连通的。
下一行包含 $$$n$$$ 整数 $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \leq s_i \leq n$$$; $$$s_i \neq s_\ell$$$ 对于所有 $$$i \neq \ell$$$)。
输出
如果没有分配边权重会产生给定数组 $$$S$$$,则输出 不可能.
否则,输出一行,其中包含 $$$m$$$ 整数 $$$w_1, w_2, \ldots, w_m$$$ ($$$1 \leq w_j \leq 10^9$$$) 作为边的权重,这样你的兄弟的错误代码会产生给定的数组 $$$S$$$。
如果有多个输出,则将接受其中任何一个。
可以证明,如果存在任何产生 $$$S$$$ 的正整数权重分配,那么对于所有 $$$j$$$ 也存在 $$$1 \le w_j \le 10^9$$$ 的分配。
示例
输入复制
5 7 3 4 2 3 1 2 3 5 1 4 1 5 4 5 1 4 3 5 2
输出复制
6 1 3 1 3 2 2
输入复制
4 4 1 2 2 3 1 3 2 4 1 3 4 2
输出复制
impossible
注意
示例输入/输出#1 的说明
图 C.1 说明了图的结构以及示例输出中边权重的分配。
![]() |
| 图 C.1:具有指定边权重的图表。 |
通过此作业,您的兄弟姐妹的错误代码运行如下:
- 最初,堆包含 $$$\{(0, 1)\}$$$。
- 从 $$$(0, 1)$$$ 开始,顶点 $$$1$$$ 第一次从堆中弹出。现在堆包含$$$\{(3, 4), (3, 2), (2, 5)\}$$$。
- 从 $$$(3, 4)$$$ 开始,顶点 $$$4$$$ 被弹出。现在堆包含$$$\{(9, 3), (6, 1), (5, 5), (3, 2), (2, 5)\}$$$。
- 从 $$$(9, 3)$$$ 开始,顶点 $$$3$$$ 被弹出。现在堆包含$$$\{(15, 4), (10, 5), (10, 2), (6, 1), (5, 5), (3, 2), (2, 5)\}$$$。
- 从 $$$(10, 5)$$$ 开始,顶点 $$$5$$$ 被弹出。现在堆包含$$$\{(12, 4), (12, 1), (11, 3), (10, 2), (6, 1), (5, 5), (3, 2), (2, 5)\}$$$。
- 从 $$$(10, 2)$$$ 开始,顶点 $$$2$$$ 被弹出。
这导致 $$$S = (1, 4, 3, 5, 2)$$$。

