.

Input

The first line contains one integer n

— the number of vertices (1≤n≤2⋅105)

.

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

If there is no pair of vertices x,y

such that g(x,y)>1, print 0. Otherwise print the maximum value of dist(x,y)

among such pairs.

Examples

3
2 3 4
1 2
2 3

1

3
2 3 4
1 3
2 3

2

3
1 1 1
1 2
2 3

0

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=;

const int inf=0x7FFFFFFF;

int Laxt[maxn],Next[maxn<<],To[maxn<<],cnt,N,sn;

int a[maxn],sz[maxn],son[maxn],vis[maxn],root,res;

int dep[maxn];

ll ans[maxn];

map<int,int>mp,tp;

map<int,int>::iterator it1,it2;

inline void read(int &x) {

    x=; char c=getchar();

    while(c>''||c<'') c=getchar();

    while(c<=''&&c>='') x=(x<<)+(x<<)+c-'',c=getchar();

}

void add(int u,int v){

    Next[++cnt]=Laxt[u];

    Laxt[u]=cnt; To[cnt]=v;

}

void getroot(int u,int fa) //找重心

{

    sz[u]=; son[u]=;

    for(int i=Laxt[u];i;i=Next[i]){

        if(To[i]!=fa&&!vis[To[i]]){

            getroot(To[i],u);

            sz[u]+=sz[To[i]];

            son[u]=max(son[u],sz[To[i]]);

        }

    }

    son[u]=max(son[u],sn-son[u]);

    if(root==||son[root]>son[u]) root=u;

}

void getans(int u,int fa,int num) //对于当前链产生的新GCD

{

    dep[u]=dep[fa]+; tp[num]=max(tp[num],dep[u]);

    for(int i=Laxt[u];i;i=Next[i]){

        if(!vis[To[i]]&&To[i]!=fa){

            getans(To[i],u,__gcd(num,a[To[i]]));

        }

    }

}

void solve(int u) //解决以u为根的子问题

{

    mp.clear(); mp[a[u]]=; ans[a[u]]++; dep[u]=;

    for(int i=Laxt[u];i;i=Next[i])

      if(!vis[To[i]]) {

         tp.clear(); getans(To[i],u,__gcd(a[u],a[To[i]]));

         for(it1=mp.begin();it1!=mp.end();it1++)

           for(it2=tp.begin();it2!=tp.end();it2++){

              int g=__gcd((*it1).first,(*it2).first);

              if(g>) res=max(res,(*it1).second+(*it2).second-);

        }

        for(it2=tp.begin();it2!=tp.end();it2++)

          mp[(*it2).first]=max((*it2).second,mp[(*it2).first]);

    }

}

void dfs(int u)  //分治

{

    vis[u]=;  solve(u);

    for(int i=Laxt[u];i;i=Next[i]){

        if(vis[To[i]]) continue;

        root=; sn=sz[To[i]];

        getroot(To[i],); dfs(root);

    }

}

int main()

{

    read(N); int u,v,Max=;

    for(int i=;i<=N;i++) read(a[i]),Max=max(Max,a[i]);

    for(int i=;i<N;i++) {

        read(u);read(v);

        add(u,v);  add(v,u);

    }

    if(Max>) res=;

    root=; sn=N; getroot(,); dfs(root);

    printf("%d\n",res);

    return ;

}