题目描述

There are $N$ junctions in Jakarta (numbered from $1$ to $N$) that are connected by $M$ bidirectional roads such that from any junction you can reach any other junctions by going through one or more roads. The $i^{th}$ junction has a height of $H_i$.

Ahmad loves to cycle, especially on flat roads. He argues that you need more power to cycle if the road is uphill or downhill. Specifically, to cycle on a road connecting junction $i$ and junction $j$, you will require a power of $|H_i - H_j|$. The required power to cycle a set of roads is equal to the highest required power to cycle each of those roads. For example, let there be $3$ roads where each requires a power of $10$, $12$, and $7$ to cycle, then the required power to cycle through all those roads is $\max(10, 12, 7) = 12$.

A cycling route from junction $i$ is defined as a tour that starts at junction $i$, going to one or more other junctions while not using the same road more than once, and ends at the same junction $i$.

Ahmad would like to find a cycling route from each junction that has a minimum required power, and that is your task in this problem. For each junction, you need to output the required power of a cycling route from that junction that has the minimum required power. There might be a case where a cycling route from a junction is not possible; in such a case, the output should be $-1$ for the respective junction.

For example, let $N = 8$, $H_{1..8} = \{5, 2, 7, 0, 10, 6, 6, 6\}$, $M = 11$, and the roads be shown in the following figure. The label on each node indicates the junction number while the number on each edge indicates the required power to cycle through that road. Notice that the required power to cycle through each road can be obtained from the given $H_{1..8}$.

:::align{center} :::

The following are the cycling routes with the minimum required power from each junction:

• Junction $1$: $1 \rightarrow 2 \rightarrow 7 \rightarrow 6 \rightarrow 1$, with a required power of $4$.
• Junction $2$: $2 \rightarrow 1 \rightarrow 6 \rightarrow 7 \rightarrow 2$, with a required power of $4$.
• Junction $3$: $3 \rightarrow 2 \rightarrow 1 \rightarrow 3$, with a required power of $5$.
• There is no possible cycling route from junction $4$.
• Junction $5$: $5 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 5$, with a required power of $8$.
• Junction $6$: $6 \rightarrow 7 \rightarrow 8 \rightarrow 6$, with a required power of $0$.
• Junction $7$: $7 \rightarrow 8 \rightarrow 6 \rightarrow 7$, with a required power of $0$.
• Junction $8$: $8 \rightarrow 6 \rightarrow 7 \rightarrow 8$, with a required power of $0$.

输入格式

Input begins with a line containing two integers $N$ $M$ ($2 \leq N \leq 100\,000$; $N-1 \leq M \leq 200\,000$) representing the number of junctions and the number of bidirectional roads, respectively. The second line contains $N$ integers $H_i$ ($0 \leq H_i \leq 10^9$) representing the height of the $i^{th}$ junction. The next $M$ lines, each contains two integers $u_i$ $v_i$ ($1 \leq u_i < v_i \leq N$) representing a bidirectional road connecting junction $u_i$ and $v_i$. It is guaranteed that from any junction you can reach any other junctions by going through one or more roads. It is also guaranteed that for any pairs of junctions $(u, v)$, there is at most one bidirectional road connecting junction $u$ and junction $v$.

输出格式

Output contains $N$ integers in a line each separated by a single space. The $i^{th}$ integer represents the required power of a cycling route from junction $i$ with the minimum required power. If there is no possible cycling route from junction $i$, then the $i^{th}$ integer is $-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