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
118
119
120
121
122
123
124
#include "bits/stdc++.h" // Tomasz Nowak
using namespace std;     // University of Warsaw
using LL = long long;
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
#define ssize(x) int(x.size())
template<class A, class B> auto& operator<<(ostream &o, pair<A, B> p) {
	return o << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &o, T x) -> decltype(x.end(), o) {
	o << '{'; int i = 0; for(auto e : x) o << (", ")+2*!i++ << e; return o << '}';
}
#ifdef DEBUG
#define debug(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n'
#else
#define debug(...) {}
#endif

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int t;
	cin >> t;
	while(t --> 0) {
		int n;
		cin >> n;
		string from, to;
		cin >> from >> to;
		vector<vector<int>> graph(n);
		REP(edge, n - 1) {
			int v, u;
			cin >> v >> u;
			--v, --u;
			graph[v].emplace_back(u);
			graph[u].emplace_back(v);
		}
		debug(graph);

		auto get_ans = [&] {
			bool from_has_0 = *min_element(from.begin(), from.end()) == '0';
			bool from_has_1 = *max_element(from.begin(), from.end()) == '1';
			bool to_has_0 = *min_element(to.begin(), to.end()) == '0';
			bool to_has_1 = *max_element(to.begin(), to.end()) == '1';
			debug(from_has_0, from_has_1, to_has_0, to_has_1);

			if(to_has_0 and to_has_1 and (not from_has_0 or not from_has_1))
				return false;
			if(from_has_0 and from_has_1 and (not to_has_0 or not to_has_1))
				return true;
			if(not to_has_0 and not from_has_0)
				return true;
			if(not to_has_1 and not from_has_1)
				return true;
			if(not from_has_1 and to_has_1)
				return false;
			if(not from_has_0 and to_has_0)
				return false;
			assert(to_has_0 and to_has_1 and from_has_0 and from_has_1);

			bool has_splitpoint_vertex = false;
			REP(v, n) {
				int cnt0 = 0, cnt1 = 0;
				for(int u : graph[v])
					++(to[u] == '1' ? cnt1 : cnt0);
				if(cnt0 > 0 and cnt1 > 0 and cnt0 + cnt1 >= 3)
					has_splitpoint_vertex = true;
			}
			if(has_splitpoint_vertex)
				return true;

			bool has_deg_geq3 = false;
			REP(v, n)
				if(ssize(graph[v]) >= 3)
					has_deg_geq3 = true;
			if(has_deg_geq3) {
				bool is_bipartite = true;
				REP(v, n)
					for(int u : graph[v])
						if(to[v] == to[u])
							is_bipartite = false;
				if(from != to and is_bipartite)
					return false;
				else
					return true;
			}
			else {
				int first = -1;
				REP(v, n)
					if(ssize(graph[v]) == 1)
						first = v;
				assert(first != -1);
				vector<bool> vis(n);
				vector<int> order = {first};
				while(ssize(order) != n) {
					int v = order.back();
					vis[v] = true;
					for(int u : graph[v])
						if(not vis[u])
							order.emplace_back(u);
				}
				debug(order);

				int cnt_from_0_to_1 = 0, cnt_from_1_to_0 = 0;
				int cnt_to_0_to_1 = 0, cnt_to_1_to_0 = 0;
				REP(i, n - 1) {
					int v = order[i];
					int u = order[i + 1];
					debug(v, u);
					cnt_from_0_to_1 += bool(from[v] == '0' and from[u] == '1');
					cnt_from_1_to_0 += bool(from[v] == '1' and from[u] == '0');
					cnt_to_0_to_1 += bool(to[v] == '0' and to[u] == '1');
					cnt_to_1_to_0 += bool(to[v] == '1' and to[u] == '0');
				}
				debug(cnt_from_0_to_1, cnt_from_1_to_0, cnt_to_0_to_1, cnt_to_1_to_0);
				if(cnt_to_1_to_0 > cnt_from_1_to_0 or cnt_to_0_to_1 > cnt_from_0_to_1
						or (cnt_to_1_to_0 == cnt_from_1_to_0 and cnt_to_0_to_1 == cnt_from_0_to_1 and from[order[0]] != to[order[0]]))
					return false;
				else
					return true;
			}
		};
		cout << (get_ans() ? "TAK" : "NIE") << '\n';
	}
}