{"raw_statement":[{"iden":"problem statement","content":"You are given an undirected tree $G$ with $N$ vertices. **The degree of every vertex in $G$ is at most $3$.**  \nThe vertices are numbered $1$ to $N$. The edges are numbered $1$ to $N-1$, and edge $i$ connects vertex $u_i$ and vertex $v_i$.  \nEach vertex has a fixed weight, and the weight of vertex $i$ is $W_i$.\nYou will add zero or more edges to $G$. The cost of adding an edge between vertex $i$ and vertex $j$ is $W_i + W_j$.\nPrint one way to add edges to satisfy the following condition for the minimum possible total cost.\n\n*   $G$ is $2$\\-vertex-connected. In other words, for every vertex $v$ in $G$, removing $v$ and its incident edges from $G$ would not disconnect $G$.\n\nYou have $T$ test cases to solve."},{"iden":"constraints","content":"*   $1 \\leq T \\leq 2 \\times 10^5$\n*   $3 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq u_i, v_i \\leq N$\n*   The given graph is a tree.\n*   The degree of every vertex in the given graph is at most $3$.\n*   $1 \\leq W_i \\leq 10^9$\n*   $W_i$ is an integer.\n*   The sum of $N$ across the test cases is at most $2 \\times 10^5$."},{"iden":"input","content":"The input is given from Standard Input in the following format, where $\\mathrm{case}_i$ represents the $i$\\-th test case:\n\n$T$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$\n$\\mathrm{case}_N$\n\nEach test case is in the following format:\n\n$N$ \n$W_1$ $W_2$ $\\dots$ $W_N$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_{N-1}$ $v_{N-1}$"},{"iden":"sample input 1","content":"2\n3\n2 3 5\n1 2\n2 3\n7\n1 10 100 1000 10000 100000 1000000\n1 2\n2 3\n2 4\n3 5\n3 6\n4 7"},{"iden":"sample output 1","content":"1\n1 3\n2\n7 6\n1 5\n\nIn the first test case, adding an edge connecting vertex $1$ and vertex $3$ makes $G$ satisfy the condition in the problem statement.  \nThe cost of this is $W_1 + W_3 = 2 + 5 = 7$. There is no way to add edges to satisfy the condition for a cost of less than $7$, so this is a valid solution.\nIn the second test case, the solution above has a total cost of $(W_7 + W_6) + (W_1 + W_5) = 1100000 + 10001 = 1110001$, which is the minimum possible."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}