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
#include <bits/stdc++.h>
using namespace std;
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef pair<ll, int> PILL;
typedef pair<ll, ll> PLL;
 
const int MAX_N = 1e6+5;
const int M = 3e4+5;
const ll INF = (ll)(1e18);
const int inf = 1e9;
const ll MOD = 1000000007LL;

void solve() {
	int n; cin >> n;
	string start, target;
	cin >> start >> target;
	vector<vector<int>> G(n);
	vector<bool> vis(n, false);
	
	for (int i = 0; i < n-1; i++) {
		int u, v;
		cin >> u >> v;
		u--; v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	
	if (n == 1) {
		if (start == target) {
			cout << "TAK\n";
		} else {
			cout << "NIE\n";
		}
		return;
	}
	
	queue<int> Q;
	for (int i = 0; i < n; i++) {
		if (G[i].size() == 1) {
			Q.push(i);
			vis[i] = true;
		}
	}
	
	while (!Q.empty()) {
		int v = Q.front();
		Q.pop();
		bool ok = (start[v] == target[v]);
		
		for (int to: G[v]) {
			if (start[to] == target[v]) ok = true;
			if (!vis[to]) {
				Q.push(to);
				vis[to] = true;
			}
		}
		
		if (!ok) {
			cout << "NIE\n";
			return;
		}
		
		start[v] = target[v];
	}
	
	cout << "TAK\n";
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
			
	int T;
	cin >> T;
	while (T--) {
		solve();
	}

	
    return 0;
}