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
#include <iostream>
#include <vector>
using namespace std;

void read_bv(vector<bool> &bv) {
	for (size_t i=0; i<bv.size(); i++) {
		char c;
		cin >> c;
		if (c == '1') {
			bv[i] = true;
		} else if (c == '0') {
			bv[i] = false;
		} else {
			cout << "bad char: " << c << "\n";
			abort();
		}
	}
}

struct node {
	vector<int> neighbors;
};

bool luz(const vector<node> &N, const vector<bool> &bv, int i, int prev) {
	bool mine = bv[i];
	for (int n: N[i].neighbors) {
		if (n == prev) continue;
		if (mine == bv[n]) return true;
		if (luz(N, bv, n, i)) return true;
	}
	return false;
}

bool test() {
	int n;
	cin >> n;
	vector<bool> from(n), to(n);
	read_bv(from);
	read_bv(to);
	vector<node> nodes(n);
	for (int i=1; i<n; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		if(a < 0 || a >= n) abort();
		if(b < 0 || b >= n) abort();
		nodes[a].neighbors.push_back(b);
		nodes[b].neighbors.push_back(a);
	}
	int fc=0, tc=0, eq=0;
	for (int i=0; i<n; i++) {
		fc += from[i];
		tc += to[i];
		eq += from[i] == to[i];
	}
	if (fc == 0) return tc == 0;
	if (fc == n) return tc == n;
	if (tc == 0 || tc == n) return true;
	if (eq == n) return true;
	bool line = true;
	int end = -1;
	for (int i=0; i<n; i++) {
		if (nodes[i].neighbors.size() > 2) line = false;
		if (nodes[i].neighbors.size() == 1) end = i;
	}
	if (end == -1) {
		cout << "no end?\n";
		abort();
	}
	if (line) {
		int i=end;
		int prev=-1;
		bool fstart = from[i];
		bool tstart = to[i];
		int ftoggles = 0;
		int ttoggles = 0;
		for (;;) {
			int next = -1;
			for (int ni: nodes[i].neighbors) {
				if (ni != prev) next = ni;
			}
			if (next == -1) break;
			prev = i;
			i = next;
			if (from[i] != from[prev]) ftoggles++;
			if (to[i] != to[prev]) ttoggles++;
		}
		return ttoggles < (ftoggles + (fstart == tstart));
	}
	return luz(nodes, to, end, -1);
}

int main() {
	int t;
	cin >> t;
	for (int i=0; i<t; i++)
		cout << (test() ? "TAK\n" : "NIE\n");
	return 0;
}