Tree Sudoku

Time limit1sMemory limit1024 MB

Summary

Assign each vertex of a tree a distinct value from sequence A so that all adjacent-pair sums are pairwise distinct, or report NO.

Level: Medium7 of 10
Topics: Tree, Greedy, Implementation
Solved: No attempts yet

Problem

Lulu, tired of ordinary Sudoku, proposed a new kind of Sudoku.

A tree with $N$ vertices and a sequence $A$ of $N$ integers are given. The $i$ -th element of sequence $A$ is $A_i$ , and all elements of $A$ are distinct.
Match every vertex of the tree with exactly one element of the sequence. That is, each vertex is matched to one element of the sequence, and no two vertices are matched to the same element.
Each vertex takes the value of its matched element. The sums of the values of every pair of adjacent vertices must all be different. In other words, the sum of any pair of adjacent vertices must differ from the sum of every other pair of adjacent vertices.

Input

The first line contains an integer $N$ . ( $2 \leq N \leq 111{,}222$ )

The second line contains the sequence $A_1, A_2, \cdots, A_N$ , separated by spaces. ( $-10^9 \leq A_i \leq 10^9$ , all elements of $A$ are distinct integers.)

The next $N-1$ lines contain the edges of the tree in the form a b. This means there is an edge connecting vertex $a$ and vertex $b$ . ( $1 \leq a, b \leq N$ )

Output

On the first line, print YES if there is a way to match the vertices and the sequence elements so that the sums of values of adjacent vertices are all different. Otherwise, print NO.

If such a way exists, print on the next line the index of the sequence element matched to each vertex, in order of vertex number, separated by spaces.

If there are several valid ways, print any of them.

Examples1

Example 1
Input
```
4
-1 1 -2 2
1 2
1 3
3 4
```
Expected output
```
YES
3 1 2 4
```