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
#include <bits/stdc++.h>
#define FOR(i, n) for(int i = 0; i < (n); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define TRAV(i, a) for(auto & i : (a))
#define SZ(x) ((int)(x).size())
#define X first
#define Y second
#define PR std::pair
#define MP std::make_pair
typedef long long ll;
typedef std::pair<int, int> PII;
typedef std::vector<int> VI;

void solve(){
	int n;
	std::cin >> n;
	std::string A, B;
	std::cin >> A >> B;
	std::vector<VI> g(n);
	bool kolo = true;
	FOR(i, n-1){
		int a, b;
		std::cin >> a >> b;
		a--;b--;
		if(B[a] == B[b]) kolo = false;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	if(kolo){
		if(A == B) std::cout << "TAK\n";
		else std::cout << "NIE\n";
		return;
	}

	int cnt[2] = {};
	FOR(i, n) cnt[B[i] == '1']++;
	if(cnt[0] == 0 || cnt[1] == 0){
		bool good = false;
		FOR(i, n) if(cnt[A[i] == '1']) good = true;
		if(good) std::cout << "TAK\n";
		else std::cout << "NIE\n";
		return;
	}
	cnt[0] = cnt[1] = 0;
	FOR(i, n) cnt[A[i] == '1']++;
	if(cnt[0] == 0 || cnt[1] == 0){
		std::cout << "NIE\n";
		return;
	}

	assert(n > 1);

	std::map<int, VI> map;
	FOR(i, n) map[SZ(g[i])].push_back(i);
	if(std::prev(map.end())->X < 3){
		assert(map.count(1));
		int v = map[1][0];
		std::vector<char> cols{B[v]};
		int last = v;
		v = g[v][0];
		while(SZ(g[v]) > 1){
			if(B[v] != cols.back()) cols.push_back(B[v]);
			std::tie(v, last) = MP(g[v][0] ^ g[v][1] ^ last, v);
		}
		if(B[v] != cols.back()) cols.push_back(B[v]);

		v = map[1][0];
		std::reverse(cols.begin(), cols.end());
		if(A[v] == cols.back()) cols.pop_back();
		last = v;
		v = g[v][0];
		while(SZ(g[v]) > 1){
			if(!cols.empty() && A[v] == cols.back()) cols.pop_back();
			std::tie(v, last) = MP(g[v][0] ^ g[v][1] ^ last, v);
		}
		if(!cols.empty() && A[v] == cols.back()) cols.pop_back();
		std::cout << (cols.empty() ? "TAK\n" : "NIE\n");
	}else{
		int v = std::prev(map.end())->Y[0];
		bool good = false;
		FOR(i, n) if(SZ(g[i]) > 1 && v != i) good = true;
		if(good){
			std::cout << "TAK\n";
			return;
		}

		cnt[0] = cnt[1] = 0;
		FOR(i, n){
			if(SZ(g[i]) == 1) cnt[B[i] == '1']++;
		}
		if(cnt[0] == 0 || cnt[1] == 0){
			if(A == B) std::cout << "TAK\n";
			else std::cout << "NIE\n";
		}else{
			std::cout << "TAK\n";
		}
	}
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);

	int t;
	std::cin >> t;
	while(t--) solve();

	return 0;
}