← 返回题目列表

Codeforces · 2206/C

C. 颠倒迪杰斯特拉

中文机器翻译题面 查看原题

你的小兄弟有一个由 $$$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:具有指定边权重的图表。

通过此作业,您的兄弟姐妹的错误代码运行如下:

  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)$$$。