题目描述

雅加达有 $N$ 个路口（编号从 $1$ 到 $N$），由 $M$ 条双向道路连接，使得从任意路口出发，可以通过一条或多条道路到达任何其他路口。第 $i$ 个路口的高度为 $H_i$。

艾哈迈德喜欢骑自行车，尤其喜欢在平坦的道路上骑行。他认为，如果道路是上坡或下坡，则需要更大的力气。具体来说，在连接路口 $i$ 和路口 $j$ 的道路上骑行所需的力气为 $|H_i - H_j|$。骑行一组道路所需的力气等于这些道路中所需力气的最大值。例如，有 $3$ 条道路，骑行每条道路分别需要 $10$、$12$ 和 $7$ 的力气，则骑行所有这些道路所需的力气为 $\max(10, 12, 7) = 12$。

从路口 $i$ 出发的骑行路线定义为一条始于路口 $i$，前往一个或多个其他路口，且不重复使用同一条道路，最后回到路口 $i$ 的环游路线。

艾哈迈德希望为每个路口找到一条所需力气最小的骑行路线，这就是本题的任务。对于每个路口，你需要输出从该路口出发的、具有最小所需力气的骑行路线所需的力气。可能存在从某个路口无法形成骑行路线的情况；此时，对应路口的输出应为 $-1$。

例如，设 $N = 8$，$H_{1..8} = \{5, 2, 7, 0, 10, 6, 6, 6\}$，$M = 11$，道路如下图所示。每个节点上的标签表示路口编号，每条边上的数字表示骑行该道路所需的力气。注意，每条道路所需的力气可由给定的 $H_{1..8}$ 计算得出。

:::align{center} :::

以下是从每个路口出发的具有最小所需力气的骑行路线：

• 路口 $1$：$1 \rightarrow 2 \rightarrow 7 \rightarrow 6 \rightarrow 1$，所需力气为 $4$。
• 路口 $2$：$2 \rightarrow 1 \rightarrow 6 \rightarrow 7 \rightarrow 2$，所需力气为 $4$。
• 路口 $3$：$3 \rightarrow 2 \rightarrow 1 \rightarrow 3$，所需力气为 $5$。
• 路口 $4$：无法形成骑行路线。
• 路口 $5$：$5 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 5$，所需力气为 $8$。
• 路口 $6$：$6 \rightarrow 7 \rightarrow 8 \rightarrow 6$，所需力气为 $0$。
• 路口 $7$：$7 \rightarrow 8 \rightarrow 6 \rightarrow 7$，所需力气为 $0$。
• 路口 $8$：$8 \rightarrow 6 \rightarrow 7 \rightarrow 8$，所需力气为 $0$。

输入格式

输入第一行包含两个整数 $N$ 和 $M$（$2 \leq N \leq 100\,000$；$N-1 \leq M \leq 200\,000$），分别表示路口数量和双向道路数量。第二行包含 $N$ 个整数 $H_i$（$0 \leq H_i \leq 10^9$），表示第 $i$ 个路口的高度。接下来 $M$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i < v_i \leq N$），表示一条连接路口 $u_i$ 和 $v_i$ 的双向道路。保证从任意路口出发，可以通过一条或多条道路到达任何其他路口。同时保证对于任意一对路口 $(u, v)$，最多有一条双向道路连接它们。

输出格式

输出一行 $N$ 个整数，每两个整数之间用一个空格隔开。第 $i$ 个整数表示从路口 $i$ 出发的具有最小所需力气的骑行路线所需的力气。如果从路口 $i$ 无法形成骑行路线，则第 $i$ 个整数为 $-1$。

8 11
5 2 7 0 10 6 6 6
1 2
1 3
2 3
2 4
2 5
2 7
3 5
1 6
6 7
6 8
7 8

4 4 5 -1 8 0 0 0

4 5
10 20 30 40
1 2
1 3
1 4
2 3
3 4

20 20 20 30

5 4
72 35 22 49 108
1 2
2 3
3 4
4 5

-1 -1 -1 -1 -1

提示

翻译由 DeepSeek 完成