You are given a tree consisting of n vertices.↵
Let's denote the function LCM(x,y) Least Common Multiple of (x,y)↵
Also let's denote dist(x,y) as the number of vertices on the simple path between vertices x and y↵
In path x to y, Neighbor verticles (a,b) all LCM(a,b)<a*b ↵
**Input**↵
n number of verticles ↵
The second line contains n integers a1, a2, ..., an (1≤ai≤2⋅105) — the numbers written on vertices.↵
Then n−1 lines follow, each containing two integers x and y (1≤x,y≤n,x≠y) denoting an edge connecting vertex x with vertex y. It is guaranteed that these edges form a tree.↵
**Output**↵
Find two verticles (x,y) tha meets the conditions.↵
↵
↵
Let's denote the function LCM(x,y) Least Common Multiple of (x,y)↵
Also let's denote dist(x,y) as the number of vertices on the simple path between vertices x and y↵
In path x to y, Neighbor verticles (a,b) all LCM(a,b)<a*b ↵
**Input**↵
n number of verticles ↵
The second line contains n integers a1, a2, ..., an (1≤ai≤2⋅105) — the numbers written on vertices.↵
Then n−1 lines follow, each containing two integers x and y (1≤x,y≤n,x≠y) denoting an edge connecting vertex x with vertex y. It is guaranteed that these edges form a tree.↵
**Output**↵
Find two verticles (x,y) tha meets the conditions.↵
↵
↵
