You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

信息组有 $n$ 个人，国庆节第 $i$ 个同学去到地点 $a_i$，$a_i$ 各不相同。老师编号为 $1$。

正常情况下， $i$ 要给 $j$ 寄东西，需要花费时间 $|a_i-a_j|$。

但是如果 $i$ 和 $j$ 之间建立了华附快线，那么寄东西的时间为 0。

东西可以从多个人之间传递。

刚过完中秋节，老师决定给每个同学发一个月饼。问老师给每个人发月饼的最短用时。

输入格式

第一行两个整数 $n$ 和 $k$，表示人数以及华附快线数量。

第二行 $n$ 个整数，$a_1 \dots a_n$。

接下来 $k$ 行，每行两个整数 $u$ 和 $v$，表示他们之间存在华附快线。

输出格式

输出 $n$ 个整数。

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

数据范围

对于所有数据 $1\le n\le 2*10^5, 0\le k \le 2*10^5$ $1\le a_i\le 10^9$

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

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

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

子任务4（29分）：$a_i=i$

子任务5（16分）：$a_i\le a_{i+1}$

子任务6（14分）