Petar is throwing a birthday party and he decided to invite some of the employees of his company where he is the CEO.

Each employee, including Petar, has a unique label from $1$ to $N$, and an accompanying type of jokes they tell $V_ i$. Also, each employee of the company except Petar has exactly one supervisor. Since Petar is the CEO of the company, he has the label $1$ and is directly or indirectly superordinate to all the employees.

At the birthday party, there are certain rules that all people present (including Petar) must follow.
 - At the party, there shouldn’t be two people that tell the same type of jokes.
 - Person $X$ cannot be invited if their direct supervisor is not invited.
 - Person $X$ cannot be invited if the set of jokes the invitees that person $X$ is superior to (directly or indirectly) tell and person $X$ don’t form a set of consecutive numbers.

The numbers in the set are consecutive if the difference between adjacent elements is exactly $1$ when the set is sorted ascendingly. For example, $(3, 1, 2)$ and $(5, 1, 2, 4, 3)$. Petar wants to know how many different sets of jokes he can see at his party with the listed constraints.

-----Input-----
The first line of input contains the integer $N$, ($1 \leq N \leq 10\ 000$). The second line of input contains $N$ integers, the types of jokes person $i$ tells, $V_ i$, ($1 \leq V_ i \leq 100$). Each of the following $N-1$ lines contains two integers $A$ and $B$, ($1 \leq A, B \leq N$), denoting that person $A$ is directly superior to person $B$.

-----Output-----
The first and only line of output must contain the number of different sets of jokes that comply to the previously listed constraints.

-----Examples-----
Sample Input 1:
4
2 1 3 4
1 2
1 3
3 4
Sample Output 1:
6

Sample Input 2:
4
3 4 5 6
1 2
1 3
2 4
Sample Output 2:
3

Source: kattis | Difficulty: HARD


Solutions: