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
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define VAR(v,w) __typeof(w) v=(w)
#define FORE(it,c) for(VAR(it,(c).begin());it!=(c).end();++it)
#define PB push_back
#define SIZE(c) ((int)(c).size())
#define CLEAR(a) memset((a), 0, sizeof(a))
#define INT(x) int x; scanf("%d", &x)

typedef vector<int> VI;
typedef vector<VI> VVI;

VVI g;
char a[100010], b[100010];
bool has[2][2];
int last;

bool alter(int v, int p, bool c) {
	if (b[v] - '0' != c) return 0;
	FORE(it,g[v]) if (*it != p && !alter(*it, v, !c)) return 0;
	return 1;
}

int parts(int v, char c[]) {
	int r = 1, p = -1;
	for (;;) {
		int w = -1;
		FORE(it,g[v]) if (*it != p) {
			w = *it;
			break;
		}
		if (w < 0) break;
		if (c[v] != c[w]) ++r;
		p = v;
		v = w;
	}
	last = v;
	return r;
}

bool go() {
	INT(n);
	scanf("\n");
	fgets(a, 100010, stdin);
	fgets(b, 100010, stdin);
	g.clear();
	g.resize(n);
	REP(i,n-1) {
		INT(x);
		INT(y);
		--x;
		--y;
		g[x].PB(y);
		g[y].PB(x);
	}
	bool d3 = 0;
	REP(i,n) if (SIZE(g[i]) >= 3) {
		d3 = 1;
		break;
	}
	if (d3) {
		CLEAR(has);
		REP(i,n) has[0][a[i] - '0'] = has[1][b[i] - '0'] = 1;
		REP(i,2) if (has[1][i] && !has[0][i]) return 0;
		bool eq = 1;
		REP(i,n) if (a[i] != b[i]) {
			eq = 0;
			break;
		}
		if (eq) return 1;
		return !alter(0, -1, b[0] - '0');
	} else {
		int s = -1;
		REP(i,n) if (SIZE(g[i]) <= 1) {
			s = i;
			break;
		}
		int a1 = parts(s, a);
		int b1 = parts(s, b);
		if (a[s] != b[s]) --a1;
		if (a[last] != b[last]) --a1;
		return a1 >= b1;
	}
}

int main() {
	INT(t);
	REP(tt,t) printf(go() ? "TAK\n" : "NIE\n");
}