Dylan是一个公司的boss。他要开一个商务party。

party上每个员工都必须讲一个笑话。不可以有两人讲同一个类型的笑话。

每个员工都有且只有一个上司(Dylan除外)。每个员工不可以出席party除非他的上司出席了这个party(Dylan一定出席)。

同时：每个人可以出席的条件是他讲的笑话必须和他的下级(直接的或间接的)讲的笑话组成了一个连续的序列。

你需要算出Dylan可以听到的笑话的组合方案数。

第一行一个整数n，表示有n个人。

接下来n个数表示每个员工讲的笑话的种类。

接下来n-1行，每行2个数a，b表示a是b的上司(Dylan 的标号为1)。

时限300ms 样例：

4
2 1 3 4
1 2
1 3
3 4 

Output：6

4
3 4 5 6
1 2
1 3
2 4  

Output：3

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

Output：10