在神奇的树の国度，叽叽 发现了一棵包含 $n$ 个节点三进制树，节点的编号是 $1 \sim n$ 。这棵树的任意一个节点的值可能为 $0, 1, 2$ 其中的一个。她喜欢有规律而不是杂乱无章的序列，她想在这棵树上找到一个路径，要满足从路径的一端到另一端，从第二个节点开始，每个节点的值都等于上一个节点的值 $+ 1$ 之后对 $3$ 取余的结果。

换言之，把路径化为一个长度为 $len$ 的序列 $G$，对于序列的第 $2 \leq i \leq len$ 项，要满足 $G_i = (G_{i - 1} + 1) \bmod 3$。例如：$2, 0, 1, 2, 0$。

现在，给出这棵三进制树，你能帮她找到最长的满足条件的路径吗，输出最长的路径长度。

输入格式

第一行输入一个整数 $n (n \leq 500000)$ 为树的节点数量。

接下来 $n - 1$ 行，每行输入两个数 $a_i$ , $b_i$ 表示编号为 $a_i$ 和 $b_i$ 的节点之间存在一条边。

接下来一行输入 $n$ 个整数 $val_j (0 \leq val_j \leq 2)$ 为第 $j$ 个节点的值。

输出格式

输出一个整数，为最大的满足条件的路径长度。

样例输入1

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

样例输出1

4

样例解释