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
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef pair <ii,int> iii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;
const int N = 100005;

int z, n, i, a, b, same, is1[2], is2[2], is[2], isGoodV, isBadV, fat, ok;
bool tab1[N], tab2[N];
VI graf[N], vec, vs;
char t1[N], t2[N];

bool check() {
	int sChanges = 0, dChanges = 0, last = -1;
	for (auto &w : vec) {
		if (last != -1) {
			if (tab1[w] != tab1[last]) sChanges++;
			if (tab2[w] != tab2[last]) dChanges++;
		}
		last = w;
	}
	if (dChanges > sChanges) return false;
	if (dChanges < sChanges) return true;
	return tab1[vec[0]] == tab2[vec[0]];
}

int main() {
scanf("%d", &z);
while (z--) {
	scanf("%d", &n);
	for (i=0;i<n;i++) graf[i].resize(0);
	scanf("%s", t1);
	scanf("%s", t2);
	for (i=0;i<n;i++) {
		tab1[i] = (t1[i] == '1');
		tab2[i] = (t2[i] == '1');
	}
	for (i=1;i<n;i++) {
		scanf("%d %d", &a, &b);
		a--;
		b--;
		graf[a].pb(b);
		graf[b].pb(a);
	}
	same = 1;
	is1[0] = is1[1] = is2[0] = is2[1] = 0;
	for (i=0;i<n;i++) {
		if (tab1[i] != tab2[i]) same = 0;
		is1[tab1[i]] = 1;
		is2[tab2[i]] = 1;
	}
	if (same) {
		printf("TAK\n");
		continue;
	}
	if ((is2[0] && !is1[0]) || (is2[1] && !is1[1])) {
		printf("NIE\n");
		continue;
	}
	
	isGoodV = 0;
	isBadV = 0;
	vs.clear();
	for (i=0;i<n;i++) if (graf[i].size() >= 3) {
		is[0] = is[1] = 0;
		for (auto& w : graf[i]) is[tab2[w]] = 1;
		if (is[0] && is[1]) isGoodV = 1;
		else if (is[0] && tab2[i] == 0) isGoodV = 1;
		else if (is[1] && tab2[i] == 1) isGoodV = 1;
		vs.pb(i);
	}
	if (isGoodV) {
		printf("TAK\n");
		continue;
	}
	if (isBadV) {
		printf("NIE\n");
		continue;
	}
	ok = 1;
	if (vs.size() == 0) {
		for (i=0;i<n;i++) if (graf[i].size() == 1) vs.pb(i);
	} else {
		ok = 0;
		for (i=0;i<n;i++) for (auto& w : graf[i]) if (tab2[i] == tab2[w]) ok = 1;
		if (ok) {
			printf("TAK\n");
			continue;
		}
	}
	for (auto& w : vs) {		
		for (auto& w2 : graf[w]) {
			vec.clear();
			vec.pb(w);
			vec.pb(w2);
			fat = w;
			while (graf[w2].size() == 2) {
				if (graf[w2][0] == fat) {
					fat = w2;
					w2 = graf[w2][1];
				} else {
					fat = w2;
					w2 = graf[w2][0];
				}
				vec.pb(w2);
			}
			//for (auto &w : vec) printf("%d ", w + 1);
			//printf("\n");
			if (!check()) ok = 0;
		}
	}
	
	if (ok) printf("TAK\n"); else printf("NIE\n");
}
return 0;
}