Today is Akshat's Birthday and he has invited some of the employees of his company which he has recently started. Every employee has a unique label from 1 to N. Akshat being the CEO, has label 1.Moreover, every employee except Akshat has exactly one superior.All the guests including the CEO, has brought some jokes $J_i$ to crack.

The party is organised keeping the following things in mind which each guest including Akshat must follow:

1. No two people should crack the same type of joke
2. An employee Y can be invited iff his direct supervisor is invited.
3. Employee Y cannot be invited if the set of jokes the invitees that person Y is superior to (directly or indirectly) tell and person Y don’t form a set of consecutive numbers

Akshat is curious to know how many different sets of jokes he can see at the party given the rules to keep in mind.

Input format

The first line contains an integer N , denoting the number of employees.

The following line contains N integers, the type of joke the ith employee brings with him $J_i$

Each of the next N-1 lines contain two integer X and Y, denoting that person X is direct senior of person Y

Output format

Output the different set of jokes that comply with the above constraints.

Constraints

• $1 <= N <= 100$
• $1 <= J_i <= 100$
• $1 <= X, Y <= N$

*Note : There is no partial scoring for this problem *