{"raw_statement":[{"iden":"problem statement","content":"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$.  \nYou are also given a length-$N$ integer sequence $A=(A_1,A_2,\\dots,A_N)$.\nFor $k = 1, 2, \\dots, N$, solve the following subproblem.\n\n> 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.\n> \n> *   $x_1, x_2, x_3, x_4$ are all distinct.\n> *   $x_1, x_2, x_3, x_4$ are all different from $k$.\n> *   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$.\n\nYou are given $t$ test cases; solve the problem for each of them."},{"iden":"constraints","content":"*   $1 \\leq t \\leq 10^5$\n*   $5 \\leq N \\leq 10^5$\n*   $1 \\leq A_i \\leq 10^9$\n*   $1 \\leq u_i \\lt v_i \\leq N$\n*   $1 \\leq b_i \\lt c_i \\leq N$\n*   $T$ and $U$ are trees.\n*   The sum of $N$ over all test cases is at most $10^5$.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format. Here, $\\mathrm{case}_i$ means the $i$\\-th test case.\n\n$t$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$\n$\\mathrm{case}_t$\n\nFor each test case, the input is given in the following format:\n\n$N$\n$A_1$ $A_2$ $\\dots$ $A_N$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_{N-1}$ $v_{N-1}$\n$b_1$ $c_1$\n$b_2$ $c_2$\n$\\vdots$\n$b_{N-1}$ $c_{N-1}$"},{"iden":"sample input 1","content":"2\n5\n20 26 1 25 213\n1 5\n3 5\n2 5\n4 5\n4 5\n1 5\n2 5\n3 5\n20\n1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288\n1 2\n2 3\n1 4\n1 5\n2 6\n3 7\n3 8\n3 9\n2 10\n1 11\n8 12\n6 13\n5 14\n11 15\n13 16\n1 17\n7 18\n9 19\n15 20\n1 2\n2 3\n2 4\n4 5\n2 6\n1 7\n6 8\n3 9\n3 10\n7 11\n7 12\n1 13\n3 14\n3 15\n8 16\n1 17\n3 18\n2 19\n1 20"},{"iden":"sample output 1","content":"\\-1 -1 -1 -1 72\n70664 616 131968 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\n\nFor 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."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}