Junji has found a beautiful tree lying on the ground, and he wants to take it home to beautify his house. However, he only plans on taking a segment of the tree because he has aichmophobia and too many branches scares him.
The tree has connection points. Each connection point has a strength,
. A good segment is a segment of the tree where every connection point on the segment has a strength that has a solution to
for some integer
. A segment of the tree is a path of the tree where every connection point is used at most once. Junji wants the longest good segment to bring home to beautify his house. Note that the longest good segment may be the entire tree, in which case he will take the entire tree home.
Input Specification
The first line will contain the integer
, the number of connection points.
The second line will contain integers,
, the strength of each connection point.
The next lines will each contain two integers
, meaning that connection point
and connection point
are connected by a single branch.
It is guaranteed that there is exactly one path between any two connection points.
Output Specification
Output the number of connection points in the longest good segment in the tree.
Constraints
Subtask 1 [10%]
All connection points satisfy the constraint for some integer
.
Subtask 2 [20%]
Subtask 3 [70%]
No additional constraints.
Sample Input 1
7
6 2 30 20 90 42 2
1 2
2 3
3 4
3 5
2 6
2 7
Sample Output 1
4
Sample Input 2
8
2 9999999900000000 3 3 3 3 3 1
1 2
1 3
3 4
4 5
3 6
2 7
2 8
Sample Output 2
2
Comments