Description

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 10000$).

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.

4
2 1 3 4
1 2
1 3
3 4

6

4
3 4 5 6
1 2
1 3
2 4

3

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

10

Scoring

In test cases worth 50% of total points, it will hold that $N$ does not exceed $100$.