你的弟弟有一个由 $n$ 个顶点和 $m$ 条边组成的连通无向图。顶点从 $1$ 到 $n$ 编号，边从 $1$ 到 $m$ 编号。第 $j$ 条边连接顶点 $u_j$ 和 $v_j$，其正整数边权为 $w_j$。

你的弟弟写了一个 Dijkstra 算法来计算从顶点 1 到所有其他顶点的最短距离，如右侧的伪代码所示。数组 $S$ 记录了每个顶点第一次从堆中弹出时的顺序。请注意，尽管每个顶点的元组可能会被多次推入堆中，但每个顶点恰好被添加到 $S$ 中一次。

然而，你的弟弟犯了一个大错。在他的代码中，堆总是弹出最大的元组，而不是最小的元组。在这里，堆按照 $(dist, u)$ 的字典序对元组进行排序，其中较大的 $dist$ 被认为更大；若 $dist$ 相同，则 $u$ 较大的元组更大。

visited ← bool array of size n, all FALSE
heap ← heap of tuples containing (0, 1)
S ← an empty array
while heap is not empty :
    (dist, u) ← top of heap
    pop top of heap
    if visited[u] = TRUE :
        continue
    visited[u] ← TRUE
    append u to the end of S
    for each v adjacent to u :
        w ← edge weight from u to v
        push tuple (dist + w, v) into heap

你的弟弟把图的结构告诉了你，即所有的无序对 $u_j$ 和 $v_j$ ($1 \le j \le m$)。然而，他没有告诉你边权 $w_j$。相反，他给了你一个数组 $S = (s_1, s_2, \dots, s_n)$，并要求你重构出这些边权。你的任务是找到一组整数边权 $w_1, w_2, \dots, w_m$ ($1 \le w_j \le 10^9$ 对于所有 $j$)，使得运行你弟弟的错误代码能够得到给定的数组 $S$。

求出任意一组满足条件的边权分配。如果不存在这样的分配，报告无解。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 100\,000$；$n - 1 \le m \le 200\,000$)。

接下来的 $m$ 行中，第 $j$ 行包含两个整数 $u_j$ 和 $v_j$ ($1 \le u_j < v_j \le n$；对于所有 $j \ne k$，$(u_j, v_j) \ne (u_k, v_k)$)。输入保证图是连通的。

最后一行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$ ($1 \le s_i \le n$；对于所有 $i \ne \ell$，$s_i \ne s_\ell$)。

输出格式

如果不存在任何边权分配能产生给定的数组 $S$，输出 impossible。

否则，输出一行，包含 $m$ 个整数 $w_1, w_2, \dots, w_m$ ($1 \le w_j \le 10^9$)，表示各条边的权重，使得你弟弟的错误代码能够产生给定的数组 $S$。

如果有多个满足条件的输出，接受其中任意一个。

可以证明，如果存在任何能够产生 $S$ 的正整数边权分配，则也必然存在一个满足对于所有 $j$ 都有 $1 \le w_j \le 10^9$ 的分配。

样例

输入样例 1

5 7
3 4
2 3
1 2
3 5
1 4
1 5
4 5
1 4 3 5 2

输出样例 1

6 1 3 1 3 2 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)$。

输入样例 2

4 4
1 2
2 3
1 3
2 4
1 3 4 2

输出样例 2

impossible