#include <bits/stdc++.h>
using namespace std;
 

ifstream fin("cerere.in");
ofstream fout("cerere.out");
 
#define cin  fin
#define cout fout
 
 
#define endl "\n"
#define ll long long

#define Nmax 100010
 
int n;

vector < int > g[Nmax];
int def[Nmax];
int sol[Nmax];
int dp[Nmax];
int grad[Nmax];
bitset < Nmax > viz;

int findBoss() {
	for(int i=1; i <= n; i++) {
		if(grad[i] == 0) {
			return i;
		}
	}
	return -1;
}

void DFS(int nod, int level) {
	viz[nod] = 1;
	dp[level] = nod;
	sol[nod] = sol [ dp[ level - def[nod] ] ] + 1;
	for(auto it : g[nod]) {
		if(viz[it] == 0) {
			DFS(it, level + 1);
		}
	}
}
 
void solve() {
	cin >> n;
	for(int i=1; i <= n; i++) {
		cin >> def[i];
		//sol[i] = -1;
	}
	for(int i=1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		grad[b]++;
	} 
	int x = findBoss();
	DFS(x, 1);
	
	for(int i=1; i <= n; i++) {
		cout << dp[i] << " ";
	}
	cout << endl;
	
	for(int i=1; i <= n; i++) {
		cout << sol[i] - 1<< " ";
	}
}
 
 
int main() {
	ios_base::sync_with_stdio(0);
	cin .tie(0);
	cout.tie(0);
	
	int testCases = 1;
	//cin >> testCases;
	while(testCases--) {
		solve();
	}
}