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
#include <bits/stdc++.h>
using namespace std;
void imax(int &a, int b){
	a=max(a, b);
}
void imin(int &a, int b){
	a=min(a, b);
}
void lmax(long long &a, long long b){
	a=max(a, b);
}
void lmin(long long &a, long long b){
	a=min(a, b);
}
/*
	WARNING: I'm using strange bracket style!
*/
const int SIZE=200000;
vector <int> graph[SIZE];
bool visited[SIZE];
vector <int> order;
int x, y, mx, root;
int col[SIZE];
string a, b;
int n, m, q;
void dfs(int u){
	visited[u]=true, order.push_back(u);
	for (auto v: graph[u])
		if (!visited[v])
			col[v]=!col[u], dfs(v);
}
int main()
	{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>q;
	while (q--)
		{
		for (int i=0; i<=n; i++)
			col[i]=false, graph[i].clear(), visited[i]=false;
		cin>>n>>a>>b, a='@'+a, b='@'+b, order.clear(), mx=0, root=0;
		for (int i=1; i<n; i++)
			cin>>x>>y, graph[x].push_back(y), graph[y].push_back(x), imax(mx, max(graph[x].size(), graph[y].size()));
		for (int i=1; i<n; i++)
			if (graph[i].size()==1)
				root=i;
		if (mx==2)
			{
			dfs(root);
			string A, B, CA, CB;
			for (int i=0; i<n; i++)
				A+=a[order[i]], B+=b[order[i]];
			A='@'+A, B='@'+B; 
			for (int i=1; i<A.size(); i++)
				{
				if (A[i]!=A[i-1])			CA+=A[i];
				if (B[i]!=B[i-1])			CB+=B[i];	
				}
			if (CA.back()!=CB.back())
				CA.pop_back();
			if (CA.size()>=CB.size())		cout<<"TAK\n";
			else							cout<<"NIE\n";
			continue;
			}
		dfs(root);
		bool hWa=false, hBa=false, hWb=false, hBb=false;
		string G1="@", G2="@";
		for (int i=1; i<=n; i++)
			G1+='0'+col[i], G2+='1'-col[i], hWa|=(a[i]=='0'), hBa|=(a[i]=='1'), hWb|=(b[i]=='0'), hBb|=(b[i]=='1');
		if ((hWb && !hWa) || (hBb && !hBa))
			{
			cout<<"NIE\n";
			continue;
			}
		if (a!=b && (b==G1 || b==G2))		cout<<"NIE\n";
		else								cout<<"TAK\n";
		}
	return 0;
	}