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
#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>
#include <climits>
#include <string>

using namespace std;

long w1[100002];
long w2[100002];

bool foo()
{
	long n;
	scanf("%ld", &n);
	string sa(n, ' ');
	string sb(n, ' ');
	scanf("%s", &sa[0]);
	scanf("%s", &sb[0]);
	if (n == 1)
		return sa.compare(sb) == 0;

	fill(w1, w1 + n + 1, 0);
	fill(w2, w2 + n + 1, 0);
	long a, b;

	long i = 1;
	for (; i < n; ++i)
	{
		scanf("%ld %ld", &a, &b);
		if (w1[a] == 0)
			w1[a] = b;
		else
		{
			if (w2[a] == 0)
				w2[a] = b;
			else
				break;
		}

		if (w2[b] == 0)
			w2[b] = a;
		else
		{
			if (w1[b] == 0)
				w1[b] = a;
			else
				break;
		}
	}

	if (i < n)
	{
		++i;
		for (; i < n; ++i)
			scanf("%ld %ld", &a, &b);

		if (sa.find('0') == string::npos || sa.find('1') == string::npos)
			return sa.compare(sb) == 0;

		return true;
	}

	for (a = 1; a <= n; ++a)
		if (w2[a] == 0 || w1[a] == 0)
			break;
	b = w1[a] + w2[a];
	long ra = 0, rb = sa[a-1] != sb[a-1];
	for (i = 1; i < n; ++i)
	{
		if (sa[a-1] != sa[b-1])
			++ra;
		if (sb[a-1] != sb[b-1])
			++rb;
		long t = a;
		a = b;
		b = w1[a] + w2[a] - t;
	}
	return ra >= rb;
}

int main()
{
	long t;
	scanf("%ld", &t);
	//long x = 1;
	while (t--)
	{
		//if (x++ == 20)
		//printf("%s\n", foo() ? "TAK" : "NIE");
		//else
		printf("%s\n", foo() ? "TAK" : "NIE");
	}
	return 0;
}