You are given a tree (undirected connected graph with no cycles) consisting of N nodes and $N - 1$ edges. There is a number associated with each node $(v_i)$ of the tree. You can break any edge of the tree you want and this would result in formation of 2 trees which were part of the original tree.

Let us denote by $treeOr$, the bitwise OR of all the numbers written on each node in a tree.

You need to find how many edges you can choose, such that, if that edge was removed from the tree, the $treeOr$ of the 2 resulting trees is equal.

Input:

First line of input contains N, the number of nodes in the tree. Next line contains N space separated integers, $i^{th}$ of which denotes $v_i$. Each of the next $N - 1$ lines describe the edges of the tree. Each line contains 2 space separated integers A and B, meaning that there is an edge between nodes A and B.

Output:

Print the number of edges that can be chosen, such that, if that edge was removed from the tree, the $treeOr$ of the 2 resulting trees is equal.

Constraints:

$2 \le N \le 2 \times 10^5$

$0 \le v_i \le 1048575$

$1 \le A , B \le N$

$A \ne B$