A tree is a connected graph with $N$ nodes and $N-1$ edges. An interesting property of trees is that there exists exactly 1 path between any two nodes.

As the top CS student in her year, Mimi's ICS teacher awards her a tree at graduation. The tree's nodes are labelled $1,2,\dots ,N$, and the $i^{\text{th}}$ node has a value, $A_i$. However, having scored only half a percentage point lower than her, you decide to contest this prize!

The teacher arranges a code-off on this tree: you are to determine the number of ordered pairs $⟨u,v⟩$ such that the values on the path match the parity of the index. Specifically, if you took the path starting from $u$ and ending at $v$ and wrote it into an array with $A_u$ as the first element and $A_v$ as the last, then the $j^{\text{th}}$ value of this array must be congruent to $jmod2$, for every $j$ from $1$ to the size of the array. Note that this array is 1-indexed.

Can you solve this problem and claim the title of top ICS student?

Constraints

For all subtasks:

$1\le A_i\le {10}^9$

Subtask 1 [10%]

$1\le N\le 500$

Subtask 2 [10%]

$1\le N\le 2000$

Subtask 3 [80%]

$1\le N\le 200000$

Input Specification

The first line of input will contain $N$, the number of nodes in the tree.
The next line of input will contain $N$ space separated integers, $A_1,A_2,\dots ,A_N$.
The next $N-1$ lines of input will each contain a pair of integers, $a_i{b}_i$, indicating that there is an edge between $a_i$ and $b_i$.

Output Specification

A single integer, the number of ordered pairs which satisfy the given condition.

Sample Input

4
1 2 3 4
1 2
2 3
3 4

Sample Output

8