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
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second

void DO() {
	int n;
	cin >> n;
	string a, b;
	cin >> a >> b;
	vector <vector <int> > graf(n);
	for (int i = 0; i < n-1; i++) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		graf[x].emplace_back(y);
		graf[y].emplace_back(x);
	}
	if (a == b) {
		cout << "TAK\n";
		return;
	}
	bool czerwone1 = false, czarne1 = false;
	bool czerwone2 = false, czarne2 = false;
	bool czydrzewo = false;
	int pocz = -1;
	for (int i = 0; i < n; i++) {
		if (a[i] == '0')
			czerwone1 = true;
		else
			czarne1 = true;
		if (b[i] == '0')
			czerwone2 = true;
		else
			czarne2 = true;
		if (graf[i].size() > 2)
			czydrzewo = true;
		if (graf[i].size() == 1)
			pocz = i;
	}
	if ((czarne2 && !czarne1) || (czerwone2 && !czerwone1)) {
		cout << "NIE\n";
		return;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < (int)graf[i].size(); j++) {
			if (b[i] == b[graf[i][j]] && czydrzewo) {
				cout << "TAK\n";
				return;
			}
		}
	}
	if (czydrzewo) {
		cout << "NIE\n";
		return;
	}
	vector <int> v(n);
	v[0] = pocz;
	for (int i = 1; i < n; i++) {
		for (auto j : graf[v[i-1]])
			if (i == 1 || j != v[i-2])
				v[i] = j;
	}
	
	int cz0 = 0, cz1 = 0;
	for (int i = 1; i < n; i++) {
		if (a[v[i]] != a[v[i-1]]) {
			if (a[v[i-1]] == '0') 
				cz0++;
			else
				cz1++;
		}
	}
	if (a[v[n-1]] == '0')
		cz0++;
	else 
		cz1++;
	
	int czb0 = 0, czb1 = 0;
	for (int i = 1; i < n; i++) {
		if (b[v[i]] != b[v[i-1]]) {
			if (b[v[i-1]] == '0') 
				czb0++;
			else
				czb1++;
		}
	}
	if (b[v[n-1]] == '0')
		czb0++;
	else 
		czb1++;

	if (czb1 > cz1 || czb0 > cz0) {
		cout << "NIE\n";
		return;
	}
	if ((czb1 == cz1) && (czb0 == cz0)) {
		if (a[v[0]] == b[v[0]])
			cout << "TAK\n";
		else
			cout << "NIE\n";
		return;
	}
	cout << "TAK\n";
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	//t = 1;
	cin >> t;
	while (t--)
		DO();
	return 0;
}