Yukikaze loves graph theory, especially forests and independent sets.
Since this problem is NP-hard for general graphs, she decides to solve a special case of the problem. We can build a special graph by the following steps. Initially, the graph consists of three vertices 1,2,3 and three edges (1,2), (2,3), (3,1). When we add a vertex xx into the graph, we select an edge (y,z) that already exists in the graph and connect (x,y) and (x,z) Keep doing this until there are n vertices in the graph.
The first line of the input contains a single integer T 1≤T≤103), indicating the number of test cases.
The first line of each test case contains a single integer n 4≤n≤105), indicating the number of vertices in the graph. It is guaranteed that the sum of nn over all test cases won't exceed 106.
The second line of each test case contains n positive integers a1,a2,…,an (1≤ai≤109), indicating the weights of the vertices.
Initially, the graph consists of three vertices 1,2,31,2,3 and three edges (1,2), (2,3), (3,1). The ii-th line of the next n-3 lines contains two integers u, v (1≤u,v<i+3), indicating the addition of a vertex i+3 and two edges (i+3,u),(i+3,v) to the graph. It is guaranteed that (u,v) already exists in the graph.
3
4
3 3 2 2
1 2
4
2 5 5 2
2 3
5
3 1 1 1 1
1 2
1 34
5
3