P15291 [MCO 2023] Love Letter

有 $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$ 所需的最少总时间。

#### 注释 第一个样例的解释： 当 $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 完成