MATOM_cpp

#include <bits/stdc++.h>
using namespace std;
#define fastIO                  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl                    '\n'
#define int long long
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

#define time__(d) \
    for ( \
        auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); \
        blockTime.second; \
        debug("%s: %lld ms\n", d, chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false \
)
const long long N=(long long)(3e5+5);
const long long M=(long long)(1e6);
const long long MOD=(long long)(1e9+7);

vector<int> adj[N];
bool vis[N];
int a[N];
int m[M+1];
vector< pair<int,int> > ans(N);

bool prime[M+1];
void sieve()
{
    memset(prime, true, sizeof(prime));
    prime[1]=false;
    for (int p=2; p*p<=M; p++)
    {
        if (prime[p] == true)
        {
            for (int i=p*p; i<=M; i += p)
                prime[i] = false;
        }
    }
}
void precalculate(){
    int x=2;
    for(int i=2;i<=M;i++){
        if(prime[i]){
            x=i;
            m[i]=x;
        }
        else{
            m[i]=x;
        }
    }
}

pair<int,int> dfs(int s, int par){
    vis[s]=true;
    int minv=m[a[s]];       //minimum energy
    int cur=s;              //node with that minimum energy

    vector< pair<int,int> > v;
    v.push_back({minv,cur});

    for(auto it:adj[s]){
        if(!vis[it]){
            pair<int,int> p=dfs(it,s);
            v.push_back(p);
        }
    }

    sort(v.begin(),v.end());

    minv=(*v.begin()).first;    //minimum energy among all nodes in the subtree
    cur=(*v.begin()).second;    //node with that minimum energy

    ans[s].first=cur;
    ans[s].second=(a[s]-minv);

    return {minv,cur};      //return it to its parent
}
void solve()
{
    int n;
    cin>>n;

    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    for(int i=1;i<=n-1;i++){
        int x,y;
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    sieve();
    precalculate();
    dfs(1,0);

    for(int i=1;i<=n;i++){
        cout<<ans[i].first<<" "<<ans[i].second<<endl;
    }
}
int32_t main()
{
    fastIO
// #ifndef ONLINE_JUDGE
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
// #endif
    int tc=1;
    // cin>>tc;
    while(tc--){
            time__("solve"){
                solve();
        }
    }

        return 0;
}