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
#include <cstdio>
#include <cstring>

using namespace std;

#define NMAX 100000

char c[NMAX+10];
char ct[NMAX+10];
int deg[NMAX+10][2];

void przypadek() {
	int n, a, b, csum = 0, ctsum = 0;
	scanf("%d %100000s %100000s ", &n, c, ct);
	for (int i = 0; i<n; ++i) {
		c[i] &= 1;
		ct[i] &= 1;
		csum += c[i];
		ctsum += ct[i];
	}
	memset(deg, 0, sizeof(int)*n*2);
	int cchange = 0, ctchange = 0, diff_leaves = 0;
	for (int i = 0; i < n-1; ++i) {
		scanf("%d%d ", &a, &b);
		--a; --b;
		deg[a][(size_t)ct[b]] += 1;
		deg[b][(size_t)ct[a]] += 1;
		if (c[a] != c[b])
			++cchange;
		if (ct[a] != ct[b])
			++ctchange;
	}
	if (csum == 0 || csum == n) {
		if (csum == ctsum)
			printf("TAK\n");
		else
			printf("NIE\n");
		return;
	}
	for (int i = 0; i < n; ++i) {
		int degt = deg[i][0] + deg[i][1];
		if (degt > 2) {
			if (deg[i][(size_t)ct[i]] > 0) {
				printf("TAK\n");
				return;
			} else if (ctchange < n-1) {
				printf("TAK\n");
				return;
			}
		}
	}
	for (int i = 0; i < n; ++i)
		if (deg[i][0] + deg[i][1] == 1 && c[i] != ct[i])
			++diff_leaves;
	if ( ctchange + diff_leaves <= cchange )
		printf("TAK\n");
	else
		printf("NIE\n");
}

int main() {
	int t;
	scanf("%d", &t);
	for (int i=0; i<t; ++i)
		przypadek();
	return 0;
}