Tree Weights

Description:

Input:

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

The $$$i$$$-th of the next $$$n-1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$, $$$u_i \ne v_i$$$).

The last line contains $$$n-1$$$ integers $$$d_1,\dots,d_{n-1}$$$ ($$$1 \le d_i \le 10^{12}$$$).

It is guaranteed that the given edges form a tree.

Output:

If there is no solution, print a single integer $$$-1$$$. Otherwise, output $$$n-1$$$ lines containing the weights $$$w_1,\dots,w_{n-1}$$$.

If there are multiple solutions, print any of them.

Sample Input:

5
1 2
1 3
2 4
2 5
31 41 59 26

Sample Output:

31
10
18
8

Sample Input:

3
1 2
1 3
18 18

Sample Output:

-1

Sample Input:

9
3 1
4 1
5 9
2 6
5 3
5 8
9 7
9 2
236 205 72 125 178 216 214 117

Sample Output:

31
41
59
26
53
58
97
93

Note:

In the first sample, the tree is as follows:

In the second sample, note that $$$w_2$$$ is not allowed to be $$$0$$$ because it must be a positive integer, so there is no solution.

In the third sample, the tree is as follows: