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 ~\langle u,v \rangle~ 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 ~j \bmod 2~, 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 2\,000~

Subtask 3 [80%]

~1 \le N \le 200\,000~

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