導入

この問題は, 現在の Cherry コンテストの前身である Zelkova コンテスト開催の際に一番最初に作問した [Zelkova 8th Tune] Black Sheep をテーマに再度作問したものです.

問題文

Black Sheep

Black Sheep において, 整数列の初項は第 $0$ 項であるとする.

$M \geq 2$ とする. 長さ $(M+1)$ の整数列 $B=(B_0, B_1, \dots, B_M)$ について, 以下を満たすような整数 $j$ が存在するとき, この整数列 $B$ は黒い列であるという.

• $0 \leq j \leq M$.
• $M$ 個の整数 $B_0, B_1, \dots, B_{j-1}, B_{j+1}, \dots, B_M$ は互いに等しく, その整数は $B_j$ とは異なる.

例えば, $(1,1,2), (3,4,3,3,3)$ は黒い列ではあるが, $(5,6,7,7,7), (8,8,9,9,9), (0,0,0,0)$ は黒い列ではない.

長さ $(M+1)$ の整数列 $C=(C_0,C_1, \dots, C_M)$ に対して, 以下の操作を$0$ 回以上行い, $C$ を黒い列にすることを目指す.

• 以下の $2$ つのうち, どちらか一方を選び, それを実行する.
• $0$ 以上 $M$ 以下の整数 $i$ を選び, $C$ の第 $i$ 項に $1$ 加算する.
• $0$ 以上 $M$ 以下の整数 $i$ を選び, $C$ の第 $i$ 項から $1$ 減算する.

$C$ を黒い列にするためには, 最低何回操作を行う必要があるか?

$(N+1)$ 頂点の単純無向グラフ $T$ が与えられる. この $T$ は木をなす.

$T$ における $(N+1)$ 個の頂点は頂点 $0,1,2, \dots, N$ と名付けられている. また, $T$ にある $N$ 本の辺のうち, $j~(1 \leq j \leq N)$ 番目の辺は頂点 $u_j$ と頂点 $v_j$ を結ぶ.

$x=1,2, \dots, N$ それぞれに対して, 以下の問いに答えよ.

• 頂点 $0$ から頂点 $x$ への単純パスを $(p_0, p_1, \dots, p_d)$ (ただし, $p_0=0, p_d=x$) とする. このとき, $d \geq 2$ か? そして, $d \geq 2$ であるならば, $C=(A_{p_0}, A_{p_1}, \dots, A_{p_d})$ に対して, Black Sheep を解け.

制約

• $1 \leq N \leq 2 \times 10^5$.
• $0 \leq A_i \leq 10^9 \quad (0 \leq i \leq N)$.
• $0 \leq u_j \leq N, 0 \leq v_j \leq N \quad (1 \leq j \leq N)$.
• $T$ は木をなす.
• 入力は全て整数である.

入力

$N$
$A_0$ $A_1$ $\cdots$ $A_N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_N$ $v_N$

出力

出力は $N$ 行からなる.

第 $x~(1 \leq x \leq N)$ 行目には, 頂点 $0$ から頂点 $x$ への単純パスを $(p_0, p_1, \dots, p_d)$ としたとき, $d \geq 2$ であるならば, $C=(A_{p_0}, A_{p_1}, \dots, A_{p_d})$ に対する, Black Sheep の解答を, $d \lt 2$ であるならば, -1 を出力せよ.

サンプル

4
3 6 1 2 7
0 1
1 2
1 3
3 4

-1
2
1
4

7
4 46 464 4646 46464 464646 4646464 46464646
0 3
0 5
3 7
4 7
1 7
2 4
4 6

4642
50642
-1
46460
-1
4688278
4642

5
1 2 4 8 16 32
0 1
0 2
0 3
0 4
0 5

-1
-1
-1
-1
-1