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
#include <bits/stdc++.h>
#define pb push_back
#define fr front()
#define ps push
#define pp pop

using namespace std;

void get(int &a) {
	char c; a=0;
	do {c=getchar_unlocked();} while ('0' > c || c > '9');
	do {a*=10; a+=c^'0'; c=getchar_unlocked();} while ('0' <= c && c <= '9');
}

int main() {
	int q;
	scanf("%d",&q);

	while (q--) {

		int n;
		scanf("%d",&n);

		char c;
		vector <bool> s;
		do {c=getchar_unlocked();} while ('0' != c && c != '1');
		do {s.pb(c^'0'); c=getchar_unlocked();} while ('0' == c || c == '1');

		vector <bool> t;
		do {c=getchar_unlocked();} while ('0' != c && c != '1');
		do {t.pb(c^'0'); c=getchar_unlocked();} while ('0' == c || c == '1');

		vector <int> r(n);
		vector <vector<int>> g(n);
		for (int i=1; i<n; i++) {
			int a,b;
			scanf("%d %d",&a,&b);
			r[a-1]++; r[b-1]++;
			g[a-1].pb(b-1);
			g[b-1].pb(a-1);
		}

		bool w=1;
		vector <bool> v(n),f(n);

		queue <int> q;
		for (int i=0; i<n; i++) if (r[i]==1) q.ps(i);

		while (!q.empty()) {
			int a=q.fr;
			q.pp();

			v[a]=1;

			if (r[a]==0) {

				if (s[a] != t[a] && !f[a]) w=0;

			} else {

				for (int i: g[a]) {

					if (!v[i]) {

						if (s[a] == t[a] || t[a] == s[i] || t[a] == t[i]) {

							if (s[a] == t[a] && s[a] == t[i]) f[i]=1;
							r[i]--;
							if (r[i]<=1) q.ps(i);

						} else  {

							w=0;
							break;

						}

					}

				}

			}
		}

		puts(w?"TAK":"NIE");

	}

	return 0;
}