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
93
94
95
96
97
#include <bits/stdc++.h>
#define qio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug(x) cerr<<#x<<" "<<x<<endl
#define ll long long 
#define st first
#define nd second
using namespace std;

int n, t, deg[100005], start, res, ile[3][3], a, b, l, r, duzy;
string pocz, kon;
vector <int> V[100005], tab, tab1, pocz1, kon1;
void DFS(int v, int par) {
	tab.push_back(pocz[v - 1] - '0');
	tab1.push_back(kon[v - 1] - '0');
	for (int i = 0; i < V[v].size(); i++) {
		if (V[v][i] != par) DFS(V[v][i], v);
	}
}

int main()
{
	qio;
	cin >> t;
	for (int i = 1; i <= t; i++) {
		cin >> n;
		cin >> pocz;
		cin >> kon;
		res = 0;
		for (int j = 1; j < n; j++) {
			cin >> a >> b;
			V[a].push_back(b);
			V[b].push_back(a);
			deg[a]++;
			deg[b]++;
		}
		for (int j = 1; j <= n; j++) {
			if (deg[j] >= 3) {
				res = 1;
			}
			if (deg[j] == n - 1) {
				res = 2;
				duzy = j;
			}
			if (deg[j] == 1) start = j;
			ile[0][pocz[j - 1] - '0']++;
			ile[1][kon[j - 1] - '0']++;
		}
		if (pocz == kon) {
			cout << "TAK" << endl;
		}
		else if ((ile[0][1] == 0 && ile[1][1] != 0) || (ile[0][0] == 0 && ile[1][0] != 0)) {
			cout << "NIE" << endl;
		}
		else if (res == 1 && ile[0][0] > 0 && ile[0][1] > 0) {
			cout << "TAK" << endl;
		}
		else if (res == 2) {
			if (ile[1][kon[duzy - 1] - '0'] == 1) cout << "NIE" << endl;
			else cout << "TAK" << endl;
		}
		else {
			DFS(start, 0);
			for (int j = 0; j < tab.size(); j++) {
				if (j == 0) pocz1.push_back(tab[j]);
				else {
					if (tab[j] != tab[j - 1]) pocz1.push_back(tab[j]);
				}
			}
			for (int j = 0; j < tab1.size(); j++) {
				if (j == 0) kon1.push_back(tab1[j]);
				else {
					if (tab1[j] != tab1[j - 1]) kon1.push_back(tab1[j]);
				}
			}
			if (pocz1[0] != kon1[0]) pocz1.pop_back();
			if (pocz1.size() >= kon1.size()) cout << "TAK" << endl;
			else cout << "NIE" << endl;

		}

		ile[0][0] = 0;
		ile[0][1] = 0;
		ile[1][0] = 0;
		ile[1][1] = 0;
		res = 0;
		if (!tab.empty()) tab.clear();
		if (!tab1.empty()) tab1.clear();
		if (!pocz1.empty()) pocz1.clear();
		if (!kon1.empty()) kon1.clear();
		for (int j = 1; j <= n; j++) {
			V[j].clear();
			deg[j] = 0;
		}
	}


}