John wants to become the president of Nicolina. We all know that the neighborhood of Nicolina can be viewed as a tree with $$$n$$$ vertices and in each vertice $$$i$$$ lives a person that has the political opinion $$$p_i$$$. To win the election one must be voted by more than $$$\frac{n}{2}$$$ inhabitants that form a continuous path in the tree. John really wants to win so he will choose a political plan $$$x$$$ such that there exists such a path of voters. John will receive a person's vote if and only if $$$x \vert p_i$$$ ($$$x$$$ divides $$$p_i$$$).
The elections are very soon and John needs to start his political campaign. Knowing the political opinions of the inhabitants and the tree that represent Nicolina, John wants to know if there exists a political plan $$$x$$$ such that there exists a continuous path of more than $$$\frac{n}{2}$$$ voters in Nicolina. Of course, John cannot choose $$$x = 1$$$ because the people in the neighborhood will think that he is dishonest.
The first line of the input contains one integer $$$n$$$ $$$( 2 \leq n \leq 2 \cdot 10^5 )$$$ - the number of vertices in Nicolina. The second line contains $$$n$$$ integers $$$p_i$$$ $$$( 2 \leq p_i \leq 10^7 ) $$$ - the political opinions of each of the inhabitants Each of the following $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ $$$(1 \leq u, v \leq n, u \neq v)$$$ - the vertices connected by an edge. It is guaranteed that these edges form a tree.
Output "YES" (without quotes) if John can win the game, and "NO" (without quotes) otherwise.
You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).
5 19 2 4 1 14 3 4 1 3 2 5 2 1
NO
7 18 2 20 14 18 13 10 7 6 3 1 5 4 4 2 5 3 3 7
YES
In the first example, John can't choose a political plan such that he wins the elections.
In the second example, John can choose $$$x = 2$$$ and there exists such path of voters. Such a path could be $$$3 - 5 - 4 - 2$$$
