Given a tree with one-way paths rooted at node ~1~ composed of ~N~ nodes each with a digit assigned to it, can a path along the tree be selected such that it starts at node ~1~ and the digits on the path can be rearranged to form a number that reads the same forwards and backwards? A path should contain at least ~1~ node.

Input Specification

The first line will contain a single integer ~N (1 \leq N \leq 10^5)~, the number of nodes in the tree.

The line will contain ~N~ space-separated digits, ~a_1~, ~a_2~, ~\ldots~, ~a_N (0 \leq a_i \leq 9)~, the ~a_i~-th digit being the digit on node ~i~.

The next ~N-1~ lines will contain two integers each, ~A~ and ~B (1 \leq A, B \leq N)~, representing a one-way path from ~A~ to ~B~.

Output Specification

Output a single integer, the number of ways a unique path along the tree can be selected such that the digits can be rearranged to form a number that reads the same fowards and backwards.

Sample Input 1

5
1 2 1 2 1
1 2
2 3
3 4
4 5

Sample Output 1

4

Sample Input 2

3
1 1 2
1 2
1 3

Sample Output 2

2