시간 제한메모리 제한제출정답맞힌 사람정답 비율
2.5 초 1024 MB77504365.152%

문제

There are $n$ dragons numbered from $1$ to $n$. Dragon $i$ has age $a_i$. The values of $a_i$ are distinct. Dragon $1$ is Evirir the dragon.

Evirir has a letter it wants to send to dragon $t$. To avoid awkwardness caused by age difference, Evirir can send the letter to another dragon (not necessarily dragon $t$). The dragon who received the letter can then send the letter to another dragon, and so on. The goal is to eventually send the letter to dragon $t$.

For all $i$ ($1 \le i \le n$), when dragon $i$ has the letter, it can send the letter to dragon $j$ in $|a_i - a_j|$ time$^1$. A dragon can "send" the letter to itself in $0$ time. However, there are $k$ pairs of dragons who are close friends. If dragons $i$ and $j$ are close friends, then it takes $0$ time instead for dragon $i$ to send a letter to dragon $j$ (and vice versa).

For each dragon $t$ ($1 \le t \le n$), answer the question (independently): What is the minimum total time needed for dragon $1$ to send a letter to dragon $t$?

$^1$Note: $|x|$ denotes the absolute value of $x$. For example, $|9| = 9$, $\lvert -6 \rvert = 6$, and $|0| = 0$. See \url{https://en.wikipedia.org/wiki/Absolute\_value} for more information.

입력

The first line contains two space-separated integers $n$ and $k$ ($1 \le n\le 2 \cdot 10^5$, $0 \le k \le 2 \cdot 10^5$) -- the number of dragons and the number of pairs of close friends.

The second line contains $n$ distinct space-separated integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) -- the dragons' ages.

Then, $k$ lines follow. Each of the $k$ lines contains two space-separated integers $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$), which means that dragons $u$ and $v$ are close friends. It is guaranteed that the same pair of close friends will not appear twice (if $(u,v)$ appears, then $(u,v)$ and $(v,u)$ will not appear afterwards).

출력

Output $n$ space-separated integers $d_1, d_2, \ldots, d_n$, where $d_i$ is the minimum total time needed for dragon $1$ to send the letter to dragon $i$.

서브태스크

번호배점제한
118

$n, k \le 2000$, $a_i = i$

214

$n, k \le 2000$

39

$k = 0$

429

$a_i = i$ for all $i$ ($1 \le i \le n$)

516

The sequence $a$ is non-decreasing, i.e. $a_i \le a_{i+1}$ for $1 \le i \le n-1$

614

No additional constraints

예제 입력 1

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

예제 출력 1

0 7 0 7 14 2 0 3

예제 입력 2

3 0
2 3 1

예제 출력 2

0 1 1

노트

Explanation for the first sample:

When $t = 1$, it takes $0$ time because dragon $1$ already has the letter.

When $t = 3$, since dragon $1$ and $3$ are close friends, dragon $1$ can send the letter directly to dragon $3$ in $0$ time.

When $t = 2$, dragon $1$ can send the letter to dragon $3$ first in $0$ time (they are close friends), then dragon $3$ sends the letter to dragon $2$ in $|23 - 30| = 7$ time. The total time taken is $0 + 7 = 7$.

When $t = 8$, dragon $1$ can just send the letter directly to dragon $8$, taking $|50 - 47| = 3$ time.

Here is one optimal way each for the remaining $t$'s ($i \xrightarrow{x} j$ means dragon $i$ sends the letter to dragon $j$ using $x$ time):

  • Dragon $4$: $1 \xrightarrow{0} 3 \xrightarrow{7} 2 \xrightarrow{0} 4$
  • Dragon $5$: $1 \xrightarrow{0} 3 \xrightarrow{7} 2 \xrightarrow{0} 4 \xrightarrow{7} 5$
  • Dragon $6$: $1 \xrightarrow{0} 3 \xrightarrow{0} 7 \xrightarrow{2} 6$
  • Dragon $7$: $1 \xrightarrow{0} 7$

채점 및 기타 정보

  • 예제는 채점하지 않는다.