You are given a tree with $N$ nodes, with the nodes numbered from $1$  to $N$ . Each node is colored either black or white, which is given to you. Find the length of the longest simple path with alternating colors(any two adjacent nodes *in the path* should have different colors).

Input format

First line has $N$.

Next $N-1$ lines each of the form u v indicating there is an edge between node u and node v.

Next N space separated booleans, ith of them represents ith node color in the tree.

Output format

Print length of the longest path.

Constraints

1 <= N <= 10^5