프라이마르팩토르

"세계에서 가장 높은 산은? 에베레스트산 정상의 가장 높은 지점. 좋아, 그럼 세계에서 두 번째로 높은 산은? 당연히 에베레스트산 정상의 두 번째로 높은 지점이지."

이 논리대로면 세계에서 가장 높은 산 목록은 아주 우스워진다. 하지만 해결책이 있는데, 바로 프라이마르팩토르(primary factor)라는 개념을 도입하는 것이다. 산의 프라이마르팩토르는 그 산에서 더 높은 산에 도달하기 위해 내려가야 하는 최소 높이 차이다. 이는 산이 얼마나 독립적인지를 나타내는 일종의 척도로 작동하며, 프라이마르팩토르가 200 m 미만인 지점을 모두 제거하면 실제로는 더 높은 산에 붙어 있는 우스운 작은 산들을 없앨 수 있다. 이 문제는 그래프에서 모든 프라이마르팩토르를 찾는 것에 관한 것이다.

$n$개의 노드와 $m$개의 간선을 가진 그래프가 있고, 각 노드 $i$에는 음이 아닌 정수 $h(i)$가 주어지며 이를 노드의 높이라고 한다. 노드의 프라이마르팩토르 $P(i)$는 노드에서 엄격히 더 높은 높이를 가진 노드에 도달하기 위해 내려가야 하는 최소 높이이다. 좀 더 수학적인 정의는 다음과 같다. $G(i)$를 노드 $i$에서 $h(j) > h(i)$인 다른 노드 $j$로 가는 모든 경로의 집합이라고 하자. $i$의 프라이마르팩토르는 다음과 같이 정의된다.

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

$G(i) = \emptyset$인 경우, 즉 더 높은 높이를 가진 노드로 아예 갈 수 없는 경우에는 프라이마르팩토르를 $h(i)$라고 한다.

그래프가 주어졌을 때, 모든 노드의 프라이마르팩토르를 구하여라.

첫째 줄에 두 정수 $n$과 $m$이 주어진다. 둘째 줄에 $n$개의 정수 $0 \leq h(i) \leq 10^9$가 주어지며, 이는 노드의 높이이다. 그다음 $m$개의 줄에 두 정수 $a$와 $b$ ($1 \leq a,b \leq n$)가 주어지며, 이는 노드 $a$와 $b$ 사이에 간선이 있음을 뜻한다.

한 줄에 $n$개의 정수를 출력한다. 이는 노드의 프라이마르팩토르이다.

• $n \le 100\,000$
• $m \le 400\,000$