CF2206C.Upside Down Dijkstra

Your little sibling has a connected undirected graph of $n$ vertices and $m$ edges. The vertices are numbered from $1$ to $n$, and the edges are numbered from $1$ to $m$. Edge $j$ connects vertices $u_j$ and $v_j$ with a positive integer weight of $w_j$.

Your little sibling coded Dijkstra's algorithm to find the shortest distances from vertex $1$ to all other vertices, as shown in the pseudocode below. The array $S$ records the order in which each vertex is popped from the heap for the first time. Note that even though tuples for each vertex may be pushed multiple times into the heap, each vertex is added to $S$ exactly once.

However, your little sibling made a big mistake. In your sibling's code, the heap always pops the maximum tuple instead of the minimum tuple. Here, the heap orders tuples lexicographically by $(\mathit{dist}, u)$, with larger $\mathit{dist}$ considered larger; ties are broken by larger $u$.

Your little sibling shares the graph structure with you, that is, all pairs of $u_j$ and $v_j$ ($1 \le j \le m$). However, your sibling does not share the edge weights $w_j$. Instead, your sibling shares an array $S = (s_1, s_2, \ldots, s_n)$ with you and asks you to reconstruct the edge weights. Your task is to find integer edge weights $w_1, w_2, \ldots, w_m$ ($1 \leq w_j \leq 10^9$ for all $j$) such that running your sibling's incorrect code yields the given array $S$.

Find any such assignment of edge weights. If no such assignment exists, report that it is impossible.

你的弟弟（或妹妹）有一个包含 $n$ 个顶点和 $m$ 条边的连通无向图。顶点编号为 $1$ 到 $n$，边编号为 $1$ 到 $m$。第 $j$ 条边连接顶点 $u_j$ 和 $v_j$，其权重为正整数 $w_j$。

你的弟弟（或妹妹）编写了 Dijkstra 算法来计算从顶点 $1$ 到其余所有顶点的最短距离，伪代码如下所示。数组 $S$ 记录了每个顶点首次从堆中被弹出的顺序。注意：尽管每个顶点可能被多次压入堆中（以不同距离值），但每个顶点在 $S$ 中恰好只出现一次。

然而，你的弟弟（或妹妹）犯了一个严重错误：在其代码中，堆总是弹出最大元组，而非最小元组。此处，堆按字典序对元组 $(\mathit{dist}, u)$ 进行排序，其中 $\mathit{dist}$ 越大则元组越大；若 $\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$（对所有 $j$ 满足 $1 \leq w_j \leq 10^9$），使得运行你弟弟（或妹妹）的错误版本代码后，恰好得到给定的数组 $S$。

请输出任意一组满足条件的边权赋值。若不存在这样的赋值，请报告“不可能”。

The first line of input contains two integers $n$ and $m$ ($2 \leq n \leq 100\,000$; $n-1 \leq m \leq 200\,000$).

The $j$-th of the next $m$ lines contains two integers $u_j$ and $v_j$ ($1 \leq u_j \lt v_j \leq n$; $(u_j, v_j) \neq (u_k, v_k)$ for all $j \neq k$). The input guarantees that the graph is connected.

The next line contains $n$ integers $s_1, s_2, \ldots, s_n$ ($1 \leq s_i \leq n$; $s_i \neq s_\ell$ for all $i \neq \ell$).

输入的第一行包含两个整数 $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$；对所有 $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$）。

If no assignment of edge weights yields the given array $S$, output impossible.

Otherwise, output a single line containing $m$ integers $w_1, w_2, \ldots, w_m$ ($1 \leq w_j \leq 10^9$) for the weights of the edges such that your sibling's incorrect code yields the given array $S$.

If there are multiple outputs, any one of them will be accepted.

It can be shown that if there exists any assignment of positive integer weights that yields $S$, then there also exists one with $1 \le w_j \le 10^9$ for all $j$.

如果不存在任何边权赋值方案能够得到给定数组 $S$，则输出 impossible。

否则，输出一行，包含 $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$ 的方案。

Explanation for the sample input/output #1

Figure C.1 illustrates the structure of the graph and the assignment of edge weights in the sample output.

Figure C.1: Graph with assigned edge weights.

With this assignment, your sibling's incorrect code runs as follows:

1. Initially, the heap contains ${(0, 1)}$.
2. From $(0, 1)$, vertex $1$ is popped from the heap for the first time. Now the heap contains ${(3, 4), (3, 2), (2, 5)}$.
3. From $(3, 4)$, vertex $4$ is popped. Now the heap contains ${(9, 3), (6, 1), (5, 5), (3, 2), (2, 5)}$.
4. From $(9, 3)$, vertex $3$ is popped. Now the heap contains ${(15, 4), (10, 5), (10, 2), (6, 1), (5, 5), (3, 2), (2, 5)}$.
5. From $(10, 5)$, vertex $5$ is popped. Now the heap contains ${(12, 4), (12, 1), (11, 3), (10, 2), (6, 1), (5, 5), (3, 2), (2, 5)}$.
6. From $(10, 2)$, vertex $2$ is popped.

This results in $S = (1, 4, 3, 5, 2)$.

样例输入/输出 #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)$。