Filling the Tree

Interview

Time limit1sMemory limit1024 MB

Summary

Decide whether the unused sticker numbers can fill a rooted tree so each parent's sticker exceeds its child's, and print one valid filling.

Level: Medium6 of 10
Topics: Greedy, Tree, Heap, DFS
Solved: No attempts yet

Problem

A tree with $N$ vertices numbered $1$ to $N$ and $N$ stickers numbered $1$ to $N$ , all distinct, are given. The tree is rooted at vertex $1$ . Dongeon wants to attach one sticker to each vertex. The parent's sticker number must be greater than the child's sticker number.

Wonbin has already attached stickers to some of the vertices. Help Dongeon determine whether the remaining stickers can be attached so the rule holds.

Input

The first line contains the number of vertices $N$ . ( $2 \le N \le 10^5$ )

The second line contains $N$ integers $a_1, \ldots, a_N$ . $a_i=0$ means vertex $i$ has no sticker yet. $1 \le a_i \le N$ means vertex $i$ already has the sticker numbered $a_i$ . Each integer from $1$ to $N$ appears at most once.

Each of the next $N-1$ lines contains two integers $u$ and $v$ ( $1 \le u, v \le N, u \ne v$ ), separated by a space, meaning there is an edge between vertex $u$ and vertex $v$ .

Output

If the stickers cannot be attached under the rule, print NO on the first line.

If they can, print YES on the first line. On the second line, print the sticker numbers on vertices $1$ through $N$ in order, separated by spaces.

If several assignments are valid, print any of them.

Examples2

Example 1

Input

12
12 10 0 2 9 5 0 0 0 0 0 0
1 2
1 3
2 4
2 5
3 6
4 7
5 8
6 9
6 10
8 11
8 12

Expected output

YES
12 10 11 2 9 5 1 8 3 4 6 7

Example 2
Input
```
6
0 3 4 0 0 0
1 2
1 3
2 4
2 5
3 6
```
Expected output
```
NO
```