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
125
126
127
128
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <limits.h>

using namespace std;

struct GraphNode{
	int initial_val;
	int target_val;
	vector<int> verticies;
};

vector<GraphNode> nodes;

bool isValidList(int beg_index){
	vector<int> ini, tar;
	int index = beg_index; 
	int prev = -1;
	for(unsigned int i = 0; i < nodes.size(); i++){
		ini.push_back(nodes[index].initial_val);
		tar.push_back(nodes[index].target_val);
		if(nodes[index].verticies.size() == 1){
			int temp = nodes[index].verticies[0];
			prev = index;
			index = temp;
		}
		else{
			int temp = nodes[index].verticies[0] == prev ? nodes[index].verticies[1] : nodes[index].verticies[0];
			prev = index;
			index = temp;
		}
	}
	
	queue<int> q;
	int last = ini[0];
	for(unsigned int i = 0; i < ini.size(); i ++){
		while(!q.empty() && q.front() == ini[i]){
			q.pop();
		}
		if(ini[i] == tar[i]){
			last = ini[i];
		}
		else{
			if(last != tar[i]){
				q.push(tar[i]);
			}
			else {
			}
		}	
	}
	return q.empty();
}




int main(){
	int t, n;
	bool init_has_red, init_has_black, target_has_red, target_has_black, is_list;
	cin >> t; 
	for(int x = 0; x < t; x++){
		nodes.clear();
		cin >> n;
		nodes.resize(n);
		init_has_black = init_has_red = target_has_black = target_has_red = false;
		
		for(int i = 0; i < n; i++) {
			char c;
			cin >> c;
			nodes[i].initial_val = c == '1' ? 1 : 0;
			init_has_black = init_has_black || nodes[i].initial_val == 1;
			init_has_red = init_has_red || nodes[i].initial_val == 0;
		}	
		for(int i = 0; i < n; i++) {
			char c;
			cin >> c;
			nodes[i].target_val = c == '1' ? 1 : 0;
			target_has_black = target_has_black || nodes[i].target_val == 1;
			target_has_red = target_has_red || nodes[i].target_val == 0;
		}
		for(int i = 0; i < n - 1; i++){
			int x,y;
			cin >> x >> y;
			nodes[x-1].verticies.push_back(y-1);
			nodes[y-1].verticies.push_back(x-1);
		}
		if(!init_has_black){
			cout << (target_has_black ? "NIE" : "TAK") << endl;
		} else if(!init_has_red){
			cout << (target_has_red ? "NIE" : "TAK") << endl;
			continue;
		} else {
			is_list = true;
			for(int i = 0; i < n && is_list; i ++){
				if(nodes[i].verticies.size() > 2) is_list = false;
			}
			if(is_list){
				bool valid = false;
				for(int i = 0; i < n && !valid; i ++){
					if(nodes[i].verticies.size() == 1){
						cout << (isValidList(i) ? "TAK" : "NIE") << endl; 
						valid = true;
					}
				}
				continue;
			}
			else{
				bool valid = false;
				for(unsigned  int i = 0; i < nodes.size() && !valid; i++){
					for(unsigned int j = 0; j < nodes[i].verticies.size() && !valid; j++){
						if(nodes[nodes[i].verticies[j]].target_val == nodes[i].target_val){
							valid = true;
						}
					}
				}
				cout << (valid ? "TAK" : "NIE") << endl;
			}
		}	
	}
	return 0;
}