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
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = b; a <= i; i--)
#define cat(x) cerr << #x << " = " << x << '\n';
using ll = long long;
using namespace std;

const int N = 100100;

int n;
vector<int> e[N], path;
char s[N], t[N];

void dfs(int u, int p) {
	path.push_back(u);
	for (auto v : e[u])
		if (v != p)
			dfs(v, u);
}

void solve() {
	cin >> n >> s + 1 >> t + 1;
	rep(i, 1, n) 
		e[i].clear();
	bool ok = false;
	rep(i, 2, n) {
		int a, b;
		cin >> a >> b;
		ok |= t[a] == t[b];
		e[a].push_back(b);
		e[b].push_back(a);
	}

	int same = 0;
	rep(i, 1, n)
		same += s[i] == t[i];

	if (same == n) {
		cout << "TAK\n";
		return;
	}

	for (auto c : {'0', '1'}) {
		if (count(t + 1, t + n + 1, c) && !count(s + 1, s + n + 1, c)) {
			cout << "NIE\n";
			return;
		}
	}

	int mx = 0;
	rep(i, 1, n)
		mx = max(mx, int(e[i].size()));

	if (mx <= 2) {
		int start = 1;
		rep(i, 1, n)
			if (e[i].size() == 1)
				start = i;
		path.clear();
		dfs(start, 0);

		int j = 0;
		for (auto u : path) {
			while (j < n && s[path[j]] != t[u])
				j++;
			if (j == n) {
				cout << "NIE\n";
				return;
			}
		}
		cout << "TAK\n";
	}
	else 
		cout << (ok ? "TAK\n" : "NIE\n");
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int t;
	cin >> t;
	while (t--) 
		solve();

	return 0;
}