1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>

using namespace std;

bool P[(int)1e5+5],K[(int)1e5+5];

int DEG[(int)1e5+5];
int main(){
ios_base::sync_with_stdio(false);
cin.tie();
cout.tie();
	int t;cin>>t;
	while(t--){
		int n;cin>>n;
		bool roz=0;
		bool trioi=0;
		bool homo=0;
		bool poli=0;
		int khetero=0,phetero=0;
		string p,k;cin>>p>>k;
		//cout<<p<<" "<<k<<"\n";
		for(int i=0;i<n;i++){
			if(p[i]=='1')P[i+1]=1;
			else P[i+1]=0;
			if(k[i]=='1')K[i+1]=1;
			else K[i+1]=0;
			if(P[i+1]!=K[i+1])roz=1;
			DEG[i+1]=0;
			if(i!=0 and P[i]!=P[i+1])poli=1;
		}
		//cout<<k[0]<<" "<<k[1]<<"\n";
		for(int i=1;i<n;i++){
			int a,b;cin>>a>>b;
			DEG[a]++;DEG[b]++;
			if(DEG[a]==3 or DEG[b]==3)trioi=1;
			if(K[a]==K[b])homo=1;
			else khetero++;
			if(P[a]!=P[b])phetero++;
			
		}
		//cout<<K[1]<<" "<<K[2]<<"\n";
		//cout<<homo<<"\n";
		bool odp=0;
		if(!roz)odp=1;
		else if(!poli)odp=0;
		else if(!homo)odp=0;
		else if(trioi)odp=1;
		else if(phetero>khetero)odp=1;
		else if(phetero<khetero)odp=0;
		else{
			for(int i=1;i<=n;i++){
				if(DEG[i]==1){
					if(P[i]==K[i])odp=1;
					break;
				}
				if(i==n)odp=1;
			}
		}
		if(odp)cout<<"TAK\n";
		else cout<<"NIE\n";
	}
	
	
	
return 0;
}