자전거 투어

자카르타에는 N개의 교차로(1번부터 N번까지 번호가 매겨져 있음)가 있고, 양방향 도로 M개로 연결되어 있다. 어느 교차로에서든 하나 이상의 도로를 거쳐 다른 모든 교차로에 갈 수 있다. i번 교차로의 높이는 $H_i$이다.

아마드는 자전거 타기를 좋아하고, 특히 평평한 도로에서 타는 것을 좋아한다. 그는 오르막이나 내리막에서는 자전거를 타는 데 더 큰 힘이 든다고 주장한다. 구체적으로, 교차로 i와 교차로 j를 잇는 도로에서 자전거를 타려면 $|H_i - H_j|$만큼의 힘이 필요하다. 도로들의 집합을 달리는 데 필요한 힘은 그 도로들 각각이 요구하는 힘 중 가장 큰 값이다. 예를 들어 도로 세 개가 각각 10, 12, 7의 힘을 요구하면, 이 세 도로를 모두 달리는 데 필요한 힘은 max(10, 12, 7) = 12이다.

교차로 i에서 출발하는 자전거 경로는 교차로 i에서 출발해 다른 교차로를 하나 이상 거치고, 같은 도로를 두 번 이상 쓰지 않으며, 다시 교차로 i에서 끝나는 주행 경로이다.

각 교차로마다 필요한 힘이 최소인 자전거 경로를 구하라. 어떤 교차로에서 자전거 경로를 만들 수 없으면 그 교차로에는 -1을 출력한다.

첫 줄에 교차로 수 N과 도로 수 M이 공백으로 구분된 두 정수로 주어진다($2 \le N \le 100000$, $N - 1 \le M \le 200000$). 둘째 줄에는 각 교차로의 높이 H_i($0 \le H_i \le 10^9$)가 N개의 정수로 주어진다. 이어지는 M개의 줄에는 각각 두 정수 u_i와 v_i($1 \le u_i < v_i \le N$)가 주어지며, 이는 교차로 u_i와 v_i를 잇는 도로를 뜻한다. 주어진 그래프는 연결되어 있다. 두 교차로를 잇는 도로는 최대 한 개이다.

N개의 정수를 한 줄에 공백 한 칸으로 구분해 출력한다. i번째 정수는 교차로 i에서 출발하는 자전거 경로 중 필요한 힘이 최소인 경로의 필요한 힘이다. 교차로 i에서 출발하는 자전거 경로가 없으면 -1을 출력한다.