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
#include <bits/stdc++.h>

using namespace std;

int main(){
	ios_base::sync_with_stdio(0);
	int t; cin>>t;
	while(t--){
		int n; cin>>n;
		vector<int> tab1, tab2;
		vector<vector<int>> graf(n);
		bool c1 = false, c2 = false;
		for(int i = 0; i < n; i++){
			char a; cin>>a;
			a-='0';
			if(a==1) c1 = true;
			else c2 = true;
			tab1.push_back(a);
		}
		bool flaga2 = false;
		for(int i = 0; i < n; i++){
			char a; cin>>a;
			a-='0';
			if(a==1&&!c1){
				flaga2 = true;
			}
			if(a==0&&!c2){
				flaga2 = true;
			}
			tab2.push_back(a);
		}
		bool flaga = false;
		for(int i = 0; i < n-1; i++){
			int a, b; cin>>a>>b;
			a--; b--;
			graf[a].push_back(b);
			graf[b].push_back(a);
		}
		for(int i = 0; i < n; i++){
			if(graf[i].size()>2) flaga = true;
		}
		if(flaga2){
			cout<<"NIE\n";
		}else if(flaga){
			cout<<"TAK\n";			
		}else{
			int idx;
			for(int i = 0; i < n; i++){
				if(graf[i].size()==1) idx = i;
			}	
			bool flaga3 = false;
			if(tab1[idx]!=tab2[idx]) flaga3 = 1;//cout<<"NIE\n";
			int ile1 = 0, ile2 = 0;
			vector<int> odw(n);
			while(idx!=-1){
				odw[idx] = true;	
				int p1 = tab1[idx];
				int p2 = tab2[idx];
				int tmp = idx;
				idx=-1;
				for(auto it:graf[tmp]){
					if(!odw[it]){
						idx = it;
						break;
					}
				}
				if(idx==-1) break;
				if(tab1[idx]!=p1) ile1++;
				if(tab2[idx]!=p2) ile2++;
			}
			ile1-=flaga3;
			if(ile2>ile1){
				cout<<"NIE\n";
			}else cout<<"TAK\n";
		}
	}
	return 0;
}