#include <bits/stdc++.h> //Grzegorz Krawczyk
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
#define rep(a,b) for(int a=0;a<int(b);a++)
#define rep2(a,b) for(int a=1;a<=(b);a++)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
const int INF=INT_MAX/2;
const LL LINF=LLONG_MAX/2;
const int LIM=1e5+7;
///flagi kompilacji:
///g++ -std=c++17 -static -Wall -pedantic -O3 -s -lm -o taj taj.cpp
struct pomocy
{
	int i;
	int lvl;
	char typ;
};
vector<int> G[LIM]; /// krawedzi wychodzace z danego wierzcholka
char type[LIM]; /// typ danego wierzcholka: = musi miec kolege tego samego poziomu, < wiekszego, > mniejszego
vector<pair<int,int>> ans; /// tu trzymam pary wierzcholkow juz sparowanych
pomocy dp[LIM]; /// trzymam kogo "przekazuje" do ojca
bool valid=1; /// czy istnieje odpowiedz
int n;

/*void debugv(vector<pair<int,int>>& v,string s)
{
	cerr<<s<<": ";
	for(auto [a,b]:v) cerr<<"{"<<a<<","<<b<<"} ";
	cerr<<"\n";
}*/

void calcdp(int ja,int oj,int cnt)
{
	if(!valid) return;
	/// kazdy vector trzyma nr i glebokosc syna o danym znaku
	vector<pair<int,int>> eq,les,mor;
	
	for(auto a:G[ja]) /// wrzucam swoich synow do wektorow
	{
		if(a==oj) continue;
		calcdp(a,ja,cnt+1);
		if(dp[a].typ=='=') eq.pb({dp[a].lvl,dp[a].i});
		else if(dp[a].typ=='<') les.pb({dp[a].lvl,dp[a].i});
		else if(dp[a].typ=='>') mor.pb({dp[a].lvl,dp[a].i});
	}
	
	/// ----- wrzucam siebie do wlasciwego wektora, potem wszystkie sortuje po glebokosciach -----
	if(type[ja]=='=') eq.pb({cnt,ja});
	else if(type[ja]=='<') les.pb({cnt,ja});
	else if(type[ja]=='>') mor.pb({cnt,ja});
	sort(eq.begin(),eq.end());
	sort(les.begin(),les.end());
	sort(mor.begin(),mor.end());
	
	/// ----- sprawdzam czy sumarycznie musze wypchnac >1 wierzcholek do ojca -----
	if(int(eq.size()%2)+abs(int(les.size())-int(mor.size()))>1)
	{
		valid=0;
		//cerr<<ja<<" w1\n";
		//debugv(eq,"eq");
		//debugv(les,"les");
		//debugv(mor,"mor");
		return;
	}
	/// ----- sprawdzam czy musze wypchnac jakis wierzcholek do ojca bedac korzeniem -----
	if(ja==1&&(int(eq.size()%2)+abs(int(les.size())-int(mor.size()))>0))
	{
		valid=0;
		//cerr<<ja<<" w2\n";
		return;
	}
	
	/// ----- rozpatruje synow z = -----
	for(int i=0;i<int(eq.size())-1;i+=2)
	{
		if(eq[i].st==eq[i+1].st)
		{
			ans.pb({eq[i].nd,eq[i+1].nd});
			continue;
		}
		if((eq.size()%2==0)||(i%2==1))
		{
			valid=0;
			//cerr<<ja<<" w3\n";
			return;
		}
		dp[ja]={eq[i].nd,eq[i].st,'='};
		i--;
	}
	if((eq.size()%2==1)&&dp[ja].i==0) dp[ja]={eq.back().nd,eq.back().st,'='};
	
	/// ----- rozpatruje synow gdy wiecej < -----
	if(les.size()>mor.size())
	{
		for(int i=(int)les.size()-1,j=(int)mor.size()-1;i>=0&&j>=0;i--,j--)
		{
			if(les[i].st<mor[j].st)
			{
				ans.pb({les[i].nd,mor[j].nd});
				continue;
			}
			if(i==j)
			{
				valid=0;
				//cerr<<ja<<" w4\n";
				return;
			}
			dp[ja]={les[i].nd,les[i].st,'<'};
			j++;
		}
		if(dp[ja].i==0) dp[ja]={les[0].nd,les[0].st,'<'};
		return;
	}
	
	/// ----- rozpatruje synow gdy wiecej > lub po rowno <> -----
	for(int i=0,j=0;i<int(les.size())&&j<int(mor.size());i++,j++)
	{
		if(les[i].st<mor[j].st)
		{
			ans.pb({les[i].nd,mor[j].nd});
			continue;
		}
		if(les.size()==mor.size()||i!=j)
		{
			valid=0;
			//cerr<<ja<<" w5\n";
			return;
		}
		dp[ja]={mor[j].nd,mor[j].st,'>'};
		i--;
	}
	if((les.size()<mor.size())&&dp[ja].i==0) dp[ja]={mor.back().nd,mor.back().st,'>'};
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n;
	rep(i,n-1)
	{
		int x;
		cin>>x;
		if(x==1) type[i+2]='=';
		else if(x==2) type[i+2]='<';
		else if(x==3) type[i+2]='>';
	}
	rep(i,n-1)
	{
		int a,b;
		cin>>a>>b;
		G[a].pb(b);
		G[b].pb(a);
	}
	calcdp(1,1,1);
	if(!valid)
	{
		cout<<"NIE\n";
		//for(auto [a,b]:ans) cerr<<a<<' '<<b<<'\n';
		return 0;
	}
	cout<<"TAK\n";
	for(auto a:ans) cout<<a.st<<' '<<a.nd<<'\n';
    return 0;
}