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
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>


using namespace std;

struct leaf {
	vector<int> children;
	int parent, depth, id, subtree;
	char color, wcolor;
	leaf() : parent(0) {};
};

bool cmpfunc(leaf a, leaf b) {
	return a.depth>b.depth;
}

bool srhtree(map<int, leaf> t,leaf l, char v, int depth) {
	if(l.depth > depth) {/*printf("NIE: %d d1 %d d2 %d\n", l.id, l.depth, depth);*/ return false;}
	if(l.color == v) {return true;}
	for(int i=0;i<l.children.size();i++)
		return srhtree(t, t[l.children[i]], v, depth);
	return false;
}

int main()
{
		int n, t;
		std::cin >> t;
		for(int _i=0;_i<t;_i++) {
			std::cin >> n;
			std::string a, b;
			std::cin >> a >> b;
			vector<leaf> tree(n+1);
			map<int, leaf> org;
			//vector<leaf> org;
			for(int i=0;i<n;i++) {
				tree[i+1].color = (a[i] == '0' ? 0 : 1);
				tree[i+1].wcolor = (b[i] == '0' ? 0 : 1);
			}
			tree[0].id = 0;
			tree[1].depth = 0;
			for(int i=0;i<n-1;i++) {
				int a1, b1;
				std::cin >> a1 >> b1;
				if(b1 < a1)
					std::swap(a1, b1);
				tree[a1].children.push_back(b1);
				tree[b1].parent = a1;
				tree[b1].depth = tree[a1].depth+1;
				tree[a1].id = a1;
				tree[b1].id = b1;
				if(!tree[a1].depth)
						tree[b1].subtree = b1;
				else tree[b1].subtree = tree[a1].subtree;
			}
			if(a == b) { std::cout << "TAK\n";  continue;}
			for(int i=0;i<tree.size();i++) {
        org[tree[i].id] = tree[i];
			}
			std::sort(tree.begin() + 1, tree.end(), cmpfunc);
			char chkzero = 0;
			for(int i=1;i<=n;i++) {
				//printf("B: %d\n", tree[i].depth);
				int j;
				if(!chkzero && (!tree[i].depth && tree[i].color == tree[i].wcolor)) goto br1;
				//if(tree[i].depth && tree[i].color == tree[i].wcolor) continue;
				//printf("EH: %d\n", tree[i].id);
				for(int j=0;j<tree[i].children.size();j++) {
					//printf("\t%d %d\n", org[tree[i].children[j]].id, org[tree[i].children[j]].color);
					if(org[tree[i].children[j]].color == tree[i].wcolor) {
							tree[i].color = tree[i].wcolor;
							org[tree[i].id].color = tree[i].wcolor;

							goto br1;
					}
				}

				if(chkzero && !tree[i].depth)
					;
				else
				for(j=n;j>=1;j--) {
						//printf("SH: %d %d\n", tree[j].depth, tree[i].depth);
					if(tree[j].depth > tree[i].depth) break;
					if(tree[j].color == tree[i].wcolor) {
						//printf("FND: %d %d\n", tree[i].id, tree[j].id);
						if(tree[i].depth > 1) {
							if(!chkzero)
								if(!srhtree(org, org[tree[i].subtree], tree[i].wcolor, tree[i].depth) && org[1].color != tree[i].wcolor) {
									chkzero = 1;
									//printf("Chk: %d %d\n", tree[i].id, tree[i].subtree, tree[i].color, tree[i].wcolor);
								}
						} else if(tree[i].depth == 1)
								if(tree[i].wcolor != org[1].color) { chkzero = 1;
							//printf("CHK0\n");
						}
						tree[i].color = tree[i].wcolor;
						org[tree[i].id].color = tree[i].wcolor;

						goto br1;
					}

				}
				//printf("ERR: %d %d %d\n", tree[i].id, tree[i].depth, tree[i].parent);
				std::cout << "NIE\n";
				goto br2;
				br1: ;
			}

			std::cout << "TAK\n";
			br2: ;
		}
    return 0;
}