No submission language available for this problem.

Description

Input

The first line contains one integer $n$ ($2 \le n \le 10^5$) — the number of vertices in the tree.

Each of the next $n - 1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$) — the ends of an edge of the tree. It's guaranteed that the given edges form a valid tree.

The last line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the numbers in the vertices.

Output

For each edge in the input order, print one number — the maximum of the $\mathrm{MAD}$ parameters of the two trees obtained after removing the given edge from the initial tree.

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

0
2
1
2

6
1 2
1 3
1 4
4 5
4 6
1 2 3 1 4 5

1
1
0
1
1

Note

In the first example, after removing edge $(1, 2)$ no number repeats $2$ times in any of the resulting subtrees, so the answer is $\max(0, 0)=0$.

After removing edge $(2, 3)$, in the bigger subtree, $1$ is repeated twice, and $2$ is repeated twice, so the $\mathrm{MAD}$ of this tree is $2$.

After removing edge $(2, 4)$, in the bigger subtree, only the number $1$ is repeated, and in the second subtree, only one number appears, so the answer is $1$.

In the second example, if edge $1 \leftrightarrow 4$ is not removed, then one of the subtrees will have two $1$, so the answer — $1$. And if edge $1 \leftrightarrow 4$ is deleted, both subtrees have no repeating values, so the answer is $0$.