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
#include <bits/stdc++.h>
using namespace std;
int st[100001], innep[100001], innek[100001];
int main() {
	ios_base::sync_with_stdio(0);
	int n, i, j, t, jedp,jedk, inw,dl, ilep, ilek, a, b;
	string p, k;
	cin >> t;
	while(t--){
		cin >> n;
		cin >> p >> k;	
		jedp = jedk = inw = 0;
		dl = p.size();
		p = '#' + p; k = '#' + k;
		for(i = 1; i < p.size();i++) {
			if(p[i] =='1') jedp++;
			if(k[i] =='1') jedk++;
			if(p[i] != k[i]) inw++;
			st[i] = 0; innep[i] = 0; innek[i] = 0;
		}
		for(i = 1; i < n; i++) {
			cin >> a >> b;
			if(p[a] != p[b]) { innep[a]++; innep[b]++;}
			if(k[a] != k[b]) { innek[a]++; innek[b]++;}
			st[a]++; st[b]++;
		}
		if(p == k) { cout <<"TAK" << endl; continue;}
		if(inw == dl) {	cout <<"NIE" << endl; continue;}
		if(jedk == 0 || jedk == dl ) { cout <<"TAK" << endl; continue;}
		if(jedp == 0 || jedp == dl ) { cout <<"NIE" << endl; continue;} 
		
		ilep = ilek = 0;
		bool pt = false, kt = true;
		for(i = 1; i <= n; i++) {
			if(innep[i] > 1) pt = true;
			if(innep[i]== 1)  ilep++;
			if(ilep > 2)  pt = true;
			if(innek[i] > 1) kt = false;
			if(innek[i]== 1)  ilek++;
			if(ilek > 2)  kt = false;
		}
		if(pt){ cout <<"TAK" << endl; continue;}
		if(kt){ cout <<"TAK" << endl; continue;}
		cout <<"NIE" << endl; 
	}
	
	
	

	
	return 0;
}