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
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second

//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

const int nax = 1e5 + 10;
int t, n;
vi V[nax];
string s_now, s_exp;
bool adjpair;

void dfs(int x, int p) {
	for(int nbh : V[x]) if(nbh != p) {
		if(s_exp[x - 1] == s_exp[nbh - 1]) adjpair = true;
		dfs(nbh, x);
	}
}

int ord[nax], nxt;

void dfs_line(int x, int p) {
	ord[nxt++] = x;
	for(int nbh : V[x]) if(nbh != p) {
		dfs_line(nbh, x);
	}
}

void solve() {
	cin >> n >> s_now >> s_exp;
	for(int i = 1; i <= n; ++i) {
		V[i].clear();
	}
	for(int u,v, i = 1; i < n; ++i) {
		cin >> u >> v;
		V[u].PB(v);
		V[v].PB(u);
	}
	if(s_now == s_exp) {
		cout << "TAK\n";
		return;
	}
	bool one = false, zero = false;
	for(auto c : s_now) {
		if(c == '1') one = true;
		else zero = true;
	}
	if(!one || !zero) {
		cout << "NIE\n";
		return;
	}
	adjpair = false;
	dfs(1, 0);
	if(!adjpair) {
		cout << "NIE\n";
		return;
	}
	bool is_line = true;
	for(int i = 1; i <= n; ++i) {
		if((int)V[i].size() > 2) {
			is_line = false;
		}
	}
	if(!is_line) {
		cout << "TAK\n";
		return;
	}
	nxt = 1;
	for(int i = 1; i <= n; ++i) {
		if((int)V[i].size() == 1) {
			dfs_line(i, 0);
			break;
		}
	}
	int diff_now = 0, diff_exp = 0;
	for(int i = 2; i <= n; ++i) {
		if(s_now[ord[i] - 1] != s_now[ord[i - 1] - 1]) {
			diff_now++;
		}
		if(s_exp[ord[i] - 1] != s_exp[ord[i - 1] - 1]) {
			diff_exp++;
		}
	}
	if(diff_exp > diff_now || (diff_exp == diff_now && s_now[ord[1] - 1] != s_exp[ord[1] - 1])) {
		cout << "NIE\n";
		return;
	}
	cout << "TAK\n";
}


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> t;
	while(t--) {
		solve();
	}
}