E. Eating The Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ nodes. Each node $$$i$$$ has an initial value $$$A_i$$$.

You can perform a special eat operation. In this operation, you select two nodes, $$$u$$$ and $$$v$$$, that are directly connected by an edge. Node $$$u$$$ can eat node $$$v$$$ only if both of the following conditions are met:

  1. The value of $$$u$$$ is strictly greater than the value of $$$v$$$ (i.e., $$$A_u \gt A_v$$$).
  2. Node $$$v$$$ is a leaf $$$^{\text{∗}}$$$ in the current state of the tree.

When $$$u$$$ eats $$$v$$$, node $$$v$$$ and the edge connecting them are removed from the tree. The value of node $$$u$$$ is then updated by absorbing $$$v$$$'s value: $$$A_u = A_u + A_v$$$.

Your task is to determine if there exists a sequence of eat operations that results in the tree being reduced to a single node. If it is possible, give any possible sequence.

$$$^{\text{∗}}$$$A leaf is a node that has exactly one edge.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ $$$(1 \le T \le 10^4)$$$. The description of the test cases follows.

The first line contains a single integer $$$N$$$ ($$$2 \le n \le 2*10^5$$$).

The second line contains $$$n$$$ space-separated integers $$$A_1, A_2, \dots, A_n$$$ ($$$1 \le A_i \le 10^9$$$), the initial values of the nodes.

The next $$$n-1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n, u \ne v$$$), describing an edge between node $$$u$$$ and node $$$v$$$ . It is guaranteed that these edges form a tree and that sum of n over all testcases doesn't exceed $$$2*10^5$$$.

Output

If it's possible to reduce the tree to a single node, first print Yes. Then, print the $$$n-1$$$ operations that achieve this. Each operation should be printed on a new line as two space-separated integers u v, where node u eats node v.

If it's impossible, print No.

Example
Input
4
5
3 9 1 2 2
4 5
4 3
1 4
2 3
5
6 6 2 8 1
2 3
2 1
2 5
4 1
3
5 6 2
3 2
2 1
2
7 3
1 2
Output
No
No
Yes
2 3
2 1
Yes
1 2