Given an undirected tree of $N$ nodes in which every node has a value. A path is called a special path if adjacent nodes in the path are of opposite parity (even then odd then even and so on). You have to find the length of the longest special path in the tree.
You can know more about a path in a tree from here.

Input
The first line contains a single integer $N$ denoting the number of nodes in the tree.
The second line contains $N$ space separated integers denoting the value of the $ith$ node.
Next $N - 1$ lines contain two space-separated integers $U$ and $V$ denoting there is an edge between node  $U$ and $V$.

Output
Print a single integer denoting the length of longest special path.

Constraints
$1 \leq N \leq10^5 \\1 \leq Value\,of\,nodes \leq10^5\\1 \leq U, V \leq N$

Author :Monu Kumar