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

vector<vector<int> > g;

int segments(int n,int v,const string &s) {
	vector<int> used(n+1);
	char z = s[v-1];
	int d=0,k=0;
	for (int i=0;i<n;i++) {
		//cout << v << " " ;
		used[v]=1;
		if (s[v-1]==z)
			d++;
		else {
			d=1;
			k++;
			z=s[v-1];
		}
		for (int j=0;j<g[v].size();j++) {
			int u = g[v][j];
			if (!used[u]) {
				v = u;
				break;
			}
		}
	}
	if (d>0)
		k++;
	return k;
}

void solve() {
	int n;
	cin >> n;
	vector<int> deg(n+1);
	g.clear();
	g.resize(n+1);
	string s1,s2;
	cin >> s1 >> s2;
	for (int i=0;i<n-1;i++) {
		int v,u;
		cin >> v >> u;
		g[v].push_back(u);
		g[u].push_back(v);
		deg[v]++;
		deg[u]++;
	}
	if (n==1) {
		cout << (s1[0]==s2[0] ? "TAK\n" : "NIE\n");
		return;
	}
	int l=0,lv[2];
	for (int i=1;i<=n;i++) {
		if (deg[i]==1) {
			l++;
			if (l<3)
				lv[l-1]=i;
		}
	}
	//cout << l << " " << lv[0] << " " << lv[1] << endl;
	if (l>2){
		int d1 = count(s1.begin(),s1.end(),'1');
		int d2 = count(s2.begin(),s2.end(),'1');
		if (d2<s2.length() && d2>0 && (d1==s1.length() || d1==0))
			cout << "NIE\n";
		else if (d2==s2.length() && d1==0 || d2==0 && d1==s1.length())
			cout << "NIE\n";
		else
			cout << "TAK\n";
	}
	else {
		int v=lv[0];
		int d1 = segments(n,v,s1);
		int d2 = segments(n,v,s2);
		if (d2<d1)
			cout << "TAK\n";
		else if (d2==d1 && s1[lv[0]-1]==s2[lv[0]-1])
			cout << "TAK\n";
		else
			cout << "NIE\n";
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	int t;
	cin >> t;
	while (t--)
		solve();
	return 0;
}