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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<bits/stdc++.h>
using namespace std;
void solve(){
	int n,i,a,b,l,c1,c2,p;
	bool same;
	char c;
	scanf("%d",&n);
	bool a1[n];
	bool a2[n];
	vector <int> G[n];
	for(i=0; i<n; i++){
		scanf(" %c",&c);
		a1[i]=(c=='1');
	}
	for(i=0;i<n;i++){
		scanf(" %c",&c);
		a2[i]=(c=='1');
	}
	for(i=0;i<n-1;i++){
		scanf("%d%d",&a,&b);
		a--;
		b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	same=true;
	for(i=0;i<n;i++)
	    if(a1[i]!=a2[i])
	same=false;
	if(same){
		printf("TAK\n");
		return;
	}
	if(n==1){
		printf("NIE\n");
		return;
	}
	l=0;
	for(i=0;i<n;i++)
	    if(G[i].size()==1)
	l++;
	if(l>2){
		same=true;
		for(i=0;i<n-1;i++)
		    if(a1[i]!=a1[i+1])
				same=false;
		if(same){
		    printf("NIE\n");
			return;
		}
		for(i=0;i<n;i++)
			for(auto ai:G[i])
				if(a2[i]==a2[ai]){
					printf("TAK\n");
					return;
				}
		printf("NIE\n");
	}
    else{
    	l=0;
    	while(G[l].size()!=1)
    	    l++;
    	c1=c2=0;
    	a=l;
    	for(i=0;i<n-1;i++){
    		if(G[a].size()==1)
    		    b=G[a][0];
    		else if(G[a][0]!=p)
    		    b=G[a][0];
    		else
    		    b=G[a][1];
			if(a1[a]!=a1[b])
				c1++;
			if(a2[a]!=a2[b])
				c2++;
			p=a;
			a=b;			 
    	}
    	if(c1>c2 || (c1==c2 && a1[l]==a2[l]))
    	    printf("TAK\n");
    	else
    	    printf("NIE\n");
    }
}
int main(){
	int t,i;
	scanf("%d",&t);
	for(i=0;i<t;i++)
	    solve();
    return 0;
}