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


bool test() {
	int n, i;
	string s1, s2;
	cin >> n;
	cin >> s1 >> s2;
	vector<vector<int>> graf;
	graf.resize(n);
	size_t m=0;
	for(i=1; i<n; ++i) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		graf[a].push_back(b);
		graf[b].push_back(a);
		m = max({m, graf[a].size(), graf[b].size()});
	}
	if(m >= 2) { // to nie jest prosta
		if(s1.find('0')==string::npos && s2.find('0')!=string::npos) return false;
		if(s1.find('1')==string::npos && s2.find('1')!=string::npos) return false;
		return true;
	}
	vector<bool> vis;
	string s1c, s2c;
	s1c.reserve(n); s2c.reserve(n);
	for(i=0;i<n; ++i)
		if(graf[i].size()==1)
			break;
	int pocz = i;
	do {
		s1c.push_back(s1[i]);
		s2c.push_back(s2[i]);
		int j = -1;
		for(auto &&e : graf[i])
			if(e!=i)
				j = e;
		i = j;
	} while(i != -1 && i != pocz);
	int pskoki = 0, dskoki = 0;
	char xd = s1c[0];
	for(auto &&e : s1c) if(e!=xd) xd = e, ++pskoki;
	xd = s2c[0];
	for(auto &&e : s2c) if(e!=xd) xd = e, ++dskoki;
	if(s1c[0] != s2c[0]) ++dskoki;
	return pskoki >= dskoki;
	
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while(t--) cout << (test()?"TAK\n":"NIE\n");
}