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

vector<int> segments(vector<vector<int>>& path, string& s, int c, int t) {
	int next, prev = -1;
	vector<int> r({0, 0});
	r[s[c] - '0']++;
	while (c != t) {
		next = path[c].front() == prev ? path[c].back() : path[c].front();
		if(s[c] != s[next])
			r[s[next] - '0']++;
		prev = c;
		c = next;
	}
	return r;
}

bool check_path(vector<vector<int>>& path, string& initial, string& required) {
	int s = -1, t = -1;
	for (int i = 0; t == -1; i++) {
		if (path[i].size() == 1) {
			if(s == -1)
				s = i;
			else
				t = i;
		}
	}
	vector<int> nsegments[2] = {segments(path, initial, s, t), segments(path, required, s, t)};
	int delta[2] = {nsegments[0][0] - nsegments[1][0], nsegments[0][1] - nsegments[1][1]};
	return delta[0] >= 0 && delta[1] >= 0 && (delta[0] > 0 || delta[1] > 0 || initial[s] == required[s]);
}

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t, n, u, v;
    string initial, required;
    cin >> t;
    while(t--) {
		cin >> n;
		cin >> initial >> required;
		bool success, mono, path = true, correct = true;
		mono = initial.find('0') == string::npos || initial.find('1') == string::npos;
		vector<vector<int>> tree(n, vector<int>());
		for (int i = 0; i < n - 1; i++) {
			cin >> u >> v;
			u--; v--;
			tree[u].push_back(v);
			tree[v].push_back(u);
			correct = required[u] != required[v] && correct;
			path = path && tree[u].size() <= 2 && tree[v].size() <= 2;
		}
		success = !(path || correct || mono) || ((correct || mono) && initial == required);
		success = success || (!(correct || mono) && path && check_path(tree, initial, required));
		cout << (success ? "TAK" : "NIE") << "\n";
	}
    return 0;
}