In the galaxy, there are ~n~ planets. Each planet may or may not have residents. Due to the vast distances in the galaxy, residents must travel from a planet to other planets through hyperspace. There are ~n-1~ bidirectional lanes in hyperspace, and the residents of the galaxy can use route ~i~ to hyperjump from planet ~u_i~ to planet ~v_i~ or vice versa. These routes ensure that from any given planet, residents can always travel to any other planet through one or more hyperjumps. Each hyperjump will cost one hyperfuel.

Believed to be dead, Sidious has unexpectedly returned and is more powerful than ever. He is hiding on one of the ~n~ planets in the galaxy. Although Rey is very worried about this return, she feels somewhat reassured knowing that she always has the support of the residents of the galaxy: for each planet that has residents, they will gather the bravest residents to one ship and travel to the planet where Sidious is by the routes in hyperspace that minimize the number of hyperjumps.

C-3PO has calculated that if Sidious is hiding on planet ~i~, traveling from other planets to planet ~i~ would cost ~a_i~ hyperfuels in total. From this information, Rey wants to determine which planets have residents or to identify if there is an error in C-3PO's calculations. As a true coder, can you help Rey?

Input

Each test contains multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 10^{4}~). The description for the test cases is as follows.

The first line of each test case contains an integer ~n~ (~1 \leq n \leq 10^6~), the number of planets in the galaxy.

The next line of each test case contains ~n~ integers ~a_1, a_2, \dots a_n~ (~0 \leq a_i \leq 10^{12}~), the amount of hyperfuels consumed if Sidious is hiding on planet ~i~, calculated by C-3PO.

For the next ~n-1~ lines, each line contains two integers ~u_i, v_i~ (~1 \leq u_i, v_i \leq n~), denoting endpoints of the ~i~-th lane in hyperspace.

It is possible to travel from any given planet to any other planet through hyperspace.

The sum of ~n~ over all test cases does not exceed ~10^6~.

Output

For each test case, if there does not exist a set of planets that is compliant with C-3PO's calculation, print a single line that contains NO.

Otherwise, print as follows.

The first line contains YES.

The next line contains ~n~ binary digits ~b_1, b_2, \dots, b_n~ (If the ~i~-th planet has residents, ~b_i=1~; otherwise, ~b_i=0~).

If there are multiple sets of planets that are compliant with C-3PO's calculation, you can output any of them.

Sample Input 1

4
4
2 5 3 3
1 2
1 3
1 4
2
1 1
1 2
2
0 0
1 2
3
1 2 1
1 2
2 3

Sample Output 1

YES
1 0 1 1 
YES
1 1 
YES
0 0 
NO

Notes

We consider the first test case.

If Sidious is hiding on planet ~1~:

• Residents from planet ~1~ do not need to make any hyperjump.

• Residents from planet ~3~ need to make ~1~ hyperjump (through lane ~2~).

• Residents from planet ~4~ need to make ~1~ hyperjump (through lane ~3~).

In total, there are ~1+1=2~ hyperjumps, which cost ~2~ hyperfuels.

If Sidious is hiding on planet ~2~:

• Residents from planet ~1~ need to make ~1~ hyperjump (through lane ~1~).

• Residents from planet ~3~ need to make ~2~ hyperjumps (through lane ~2~ then lane ~1~).

• Residents from planet ~4~ need to make ~2~ hyperjumps (through lane ~3~ then lane ~1~).

In total, there are ~1+2+2=5~ hyperjumps, which cost ~5~ hyperfuels.

If Sidious is hiding on planet ~3~:

• Residents from planet ~1~ need to make ~1~ hyperjump (through lane ~2~).

• Residents from planet ~3~ do not need to make any hyperjump.

• Residents from planet ~4~ need to make ~2~ hyperjumps (through lane ~3~ then lane ~2~).

In total, there are ~1+2=3~ hyperjumps, which cost ~3~ hyperfuels.

If Sidious is hiding on planet ~3~:

• Residents from planet ~1~ need to make ~1~ hyperjump (through lane ~3~).

• Residents from planet ~3~ need to make ~2~ hyperjumps (through lane ~2~ then lane ~3~).

• Residents from planet ~4~ do not need to make any hyperjumps.

In total, there are ~1+2=3~ hyperjumps, which cost ~3~ hyperfuels.