Ternary Cycle

Problem Description

In the magical Tree Kingdom, Jiji discovered a ternary tree with $n$ nodes, numbered $1 \sim n$. The value of any node can be one of $0, 1, 2$. She likes regular rather than chaotic sequences. She wants to find a path on this tree such that, from one end of the path to the other, starting from the second node, each node's value equals the value of the previous node plus $1$ modulo $3$.

In other words, if we turn the path into a sequence $G$ of length $len$, then for every $2 \le i \le len$ we must have $G_i = (G_{i-1} + 1) \bmod 3$. For example: $2, 0, 1, 2, 0$.

Now, given this ternary tree, can you help her find the longest valid path? Output the maximum length of such a path.

Input Format

The first line contains an integer $n$ ($n \le 500000$), the number of nodes in the tree.

The next $n-1$ lines each contain two integers $a_i, b_i$, indicating an edge between nodes $a_i$ and $b_i$.

The next line contains $n$ integers $val_j$ ($0 \le val_j \le 2$), the value of the $j$-th node.

Output Format

Output one integer: the maximum length of a valid path.

Sample Input

8
1 2
1 3
2 4
2 5
3 6
5 7
5 8
2 1 1 0 2 1 2 0

Sample Output

4

Sample Explanation