Problem Statement

You are given two trees $T$ and $U$, each with $N$ vertices numbered from $1$ to $N$. The $i$-th edge of $T$ connects vertices $u_i$ and $v_i$. The $i$-th edge of $U$ connects vertices $b_i$ and $c_i$. You are also given a length-$N$ integer sequence $A=(A_1,A_2,\dots,A_N)$.

For $k = 1, 2, \dots, N$, solve the following subproblem.

Does there exist a tuple of integers $(x_1, x_2, x_3, x_4)$ that satisfies the following conditions? If so, find the minimum value of $\sum_{i=1}^4 A_{x_i}$ for a tuple satisfying the conditions.

• $x_1, x_2, x_3, x_4$ are all distinct.
• $x_1, x_2, x_3, x_4$ are all different from $k$.
• For all integers $(i,j)$ satisfying $1 \leq i \lt j \leq 4$, the $x_i x_j$ path in $T$ contains vertex $k$, and the $x_i x_j$ path in $U$ also contains vertex $k$.

You are given $t$ test cases; solve the problem for each of them.

Constraints

• $1 \leq t \leq 10^5$
• $5 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq u_i \lt v_i \leq N$
• $1 \leq b_i \lt c_i \leq N$
• $T$ and $U$ are trees.
• The sum of $N$ over all test cases is at most $10^5$.
• All input values are integers.

Input

The input is given from Standard Input in the following format. Here, $\mathrm{case}_i$ means the $i$-th test case.

t
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_t

For each test case, the input is given in the following format:

N
A_1 A_2 \dots A_N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
b_1 c_1
b_2 c_2
\vdots
b_{N-1} c_{N-1}

Output

Output $t$ lines. The $i$-th line should contain the answer for the $i$-th test case. For each test case, output the answers to the subproblems in the order $k=1,2,\dots,N$, separated by spaces on one line. For each subproblem, output $-1$ if there does not exist a tuple of integers $(x_1, x_2, x_3, x_4)$ satisfying the conditions, or output the minimum value of $\sum_{i=1}^4 A_{x_i}$ for such a tuple if it exists.