MATOM_t_py

import sys

maxN = 3 * 100100
sys.setrecursionlimit(3 * 100100)

def fast_input():
    return sys.stdin.readline()


is_prime = [True for i in range(1000100)]
prime_less = [i for i in range(1000100)]

is_prime[0] = is_prime[1] = False

for i in range(2, int(1000100**0.5) + 1):
    if is_prime[i]:
        for j in range(i*i,1000100,i):
            is_prime[j] = False


for i in range(2, 1000100):
    prime_less[i] = prime_less[i-1]
    if is_prime[i]:
        prime_less[i] = i;

n = int(fast_input())
adj = [[] for i in range(n + 1)]
final_score = [0 for i in range(n + 1)]
initial_score = [0]
transition_score = [0 for i in range(n + 1)]
final_node = [i for i in range(n + 1)]

def dfs(node, par):
    min_score = final_score[node]
    curr_node = node

    for child in adj[node]:
        if child != par:
            dfs(child, node)
            if final_score[child] < min_score :
                min_score = final_score[child]
                curr_node = final_node[child]

            elif final_score[child] == min_score:
                if curr_node > final_node[child]:
                    curr_node = final_node[child]


    final_node[node] = curr_node
    final_score[node] = min_score

initial_score = initial_score + list(map(int,fast_input().split()))

assert len(initial_score) == n + 1

for i in range(1, n + 1):
    transition_score[i] = prime_less[initial_score[i]]
    final_score[i] = transition_score[i]


for i in range(1,n):
    u,v = list(map(int,fast_input().split()))
    adj[u].append(v)
    adj[v].append(u)


dfs(1, 1)

for i in range(1, n + 1):
    print(final_node[i], initial_score[i] - final_score[i])