AT_arc213_c [ARC213C] Double X

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.

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 $ 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.

### Sample Explanation 1 For the first test case, when $ k=1,2,3,4 $ , there does not exist $ (x_1, x_2, x_3, x_4) $ satisfying the conditions. When $ k=5 $ , $ (x_1,x_2,x_3,x_4) = (1,2,3,4) $ satisfies the conditions. ### 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.