돌출도

“세계에서 가장 높은 산은 무엇일까? Mount Everests 정상에서 가장 높은 지점이다. OK, 그렇다면 세계에서 두 번째로 높은 산은 무엇일까? 물론 Mount Everests 정상에서 두 번째로 높은 지점이다.”

이 논리에 따르면 세계에서 가장 높은 산의 목록은 매우 우스워진다. 하지만 해결책이 있다. 돌출도라는 개념을 도입하는 것이다. 산의 돌출도는 그 산에서 엄밀히 더 높은 산에 도달하기 위해 고도상 내려가야 하는 최소 거리이다. 이는 산이 얼마나 독립적인지를 나타내는 일종의 척도이며, 돌출도가 200 m 미만인 모든 지점을 제거하면 실제로는 더 높은 산에 붙어 있는 우스꽝스러운 작은 산을 모두 없앨 수 있다. 이 문제는 그래프에서 모든 돌출도를 찾는 문제이다.

각 정점 $i$에 그 정점의 높이인 음이 아닌 정수 $h(i)$이 주어진, 정점 $n$개와 간선 $m$개로 이루어진 그래프가 있다. 정점의 돌출도 $P(i)$은 그 정점에서 높이가 엄밀히 더 높은 정점에 도달하기 위해 내려가야 하는 최소 높이이다. 이를 조금 더 수학적으로 정의하면 다음과 같다. $G(i)$를 정점 $i$에서 $h(j) > h(i)$를 만족하는 어떤 다른 정점 $j$까지의 모든 경로의 집합이라고 하자. $i$의 돌출도는 다음과 같이 정의한다.

$\begin{aligned}P(i) = \min_{\gamma \in G(i)} \left\{ h(i) - \min_{k\in \gamma}(h(k)) \right\}\end{aligned}$

$G(i) = \emptyset$인 경우, 즉 높이가 더 높은 정점에 도달하는 것이 아예 불가능한 경우에는 돌출도가 $h(i)$이라고 한다.

그래프가 주어질 때 모든 정점의 돌출도를 구하여라.

채점

여러 테스트 케이스 그룹으로 제출한 풀이를 평가한다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

1      |  25  |  $n \le 1000, m \le 4000$

2      |  25  |  $n \le 100\,000,$ 그래프는 선형이다. 즉, 간선은 $(1,2),(2,3) \dots (n-1,n)$이다

3      |  50  |  $n \le 100\,000, m \le 400\,000$

두 정수 $n$와 $m$가 한 줄에 주어진다. 정점들의 높이를 나타내는 정수 $0 \leq h(i) \leq 10^9$ $n$개가 한 줄에 주어진다. 이어지는 $m$개의 줄에는 두 정수 $a$와 $b$ ($1 \leq a,b \leq n$)가 주어지며, 이는 정점 $a$와 $b$ 사이에 간선이 있음을 의미한다.

정점들의 돌출도를 나타내는 정수 $n$개를 한 줄에 출력한다.