题目描述

有 $n$ 条龙，编号从 $1$ 到 $n$。第 $i$ 条龙的年龄为 $a_i$。$a_i$ 的值互不相同。龙 $1$ 是巨龙 Evirir。

Evirir 有一封信想寄给龙 $t$。为了避免因年龄差异带来的尴尬，Evirir 可以将信件寄给另一条龙（不一定是龙 $t$）。收到信件的龙可以再将信件寄给其他龙，以此类推。最终的目标是将信件送达龙 $t$。

对于所有 $i$ （$1 \le i \le n$），当龙 $i$ 持有信件时，它可以将信件寄给龙 $j$，耗时 $|a_i - a_j|$ $^1$。一条龙可以花费 $0$ 时间将信件“寄”给自己。然而，有 $k$ 对龙是亲密好友。如果龙 $i$ 和龙 $j$ 是亲密好友，那么龙 $i$ 寄信给龙 $j$（反之亦然）所需时间则为 $0$。

对于每条龙 $t$ （$1 \le t \le n$），请（独立地）回答以下问题：龙 $1$ 将一封信寄到龙 $t$ 所需的最少总时间是多少？

$^1$ 注： $|x|$ 表示 $x$ 的绝对值。例如， $|9| = 9$， $\lvert -6 \rvert = 6$， $|0| = 0$。

输入格式

第一行包含两个以空格分隔的整数 $n$ 和 $k$ （$1 \le n\le 2 \cdot 10^5$， $0 \le k \le 2 \cdot 10^5$）—— 分别表示龙的数量和亲密好友的对数。

第二行包含 $n$ 个 互不相同 的、以空格分隔的整数 $a_1, a_2, \ldots, a_n$ （$1 \le a_i \le 10^9$）—— 每条龙的年龄。

接下来 $k$ 行，每行包含两个以空格分隔的整数 $u$ 和 $v$ （$1 \le u, v \le n$， $u \ne v$），表示龙 $u$ 和龙 $v$ 是亲密好友。保证同一对亲密好友不会出现两次（如果 $(u,v)$ 出现，则后续不会再次出现 $(u,v)$ 或 $(v,u)$）。

输出格式

输出 $n$ 个以空格分隔的整数 $d_1, d_2, \ldots, d_n$，其中 $d_i$ 表示龙 $1$ 将信件寄到龙 $i$ 所需的最少总时间。

8 4
50 30 23 10 3 67 69 47
3 7
3 1
2 4
7 1

0 7 0 7 14 2 0 3

3 0
2 3 1

0 1 1

提示

注释

第一个样例的解释：

当 $t = 1$ 时，耗时为 $0$，因为龙 $1$ 已经持有信件。

当 $t = 3$ 时，由于龙 $1$ 和龙 $3$ 是亲密好友，龙 $1$ 可以直接寄信给龙 $3$，耗时 $0$。

当 $t = 2$ 时，龙 $1$ 可以先将信寄给龙 $3$，耗时 $0$（它们是亲密好友），然后龙 $3$ 将信寄给龙 $2$，耗时 $|23 - 30| = 7$。总耗时为 $0 + 7 = 7$。

当 $t = 8$ 时，龙 $1$ 可以直接寄信给龙 $8$，耗时 $|50 - 47| = 3$。

以下是其余 $t$ 值各自的一种最优方案（$i \xrightarrow{x} j$ 表示龙 $i$ 寄信给龙 $j$，耗时 $x$）：

• 龙 $4$： $1 \xrightarrow{0} 3 \xrightarrow{7} 2 \xrightarrow{0} 4$
• 龙 $5$： $1 \xrightarrow{0} 3 \xrightarrow{7} 2 \xrightarrow{0} 4 \xrightarrow{7} 5$
• 龙 $6$： $1 \xrightarrow{0} 3 \xrightarrow{0} 7 \xrightarrow{2} 6$
• 龙 $7$： $1 \xrightarrow{0} 7$

计分

子任务 1 （$18$ 分）： $n, k \le 2000$， $a_i = i$

子任务 2 （$14$ 分）： $n, k \le 2000$

子任务 3 （$9$ 分）： $k = 0$

子任务 4 （$29$ 分）： 对于所有 $i$ （$1 \le i \le n$），有 $a_i = i$

子任务 5 （$16$ 分）： 序列 $a$ 是非递减的，即对于 $1 \le i \le n-1$，有 $a_i \le a_{i+1}$

子任务 6 （$14$ 分）： 无额外限制

翻译由 DeepSeek 完成