Niestety, nie byliśmy w stanie w pełni poprawnie wyświetlić tego pliku, ponieważ nie jest zakodowany w UTF-8. Możesz pobrać ten plik i spróbować otworzyć go samodzielnie. 
  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
#include <iostream>
#include <vector>
using namespace std;

vector<int> tab[100007];

char kol(string s) { // zwraca kolor kt�rego s nie zawiera je�li jednokolorowe, wpp 0
	for (int i = 1; i < s.length(); i++) {
		if (s[i] != s[i - 1]) return 0;
	}
	if (s[0] == '1') return '0';
	return '1';
}

bool zawiera(string s, char c) {
	for (int i = 0; i < s.length(); i++) {
		if (s[i] == c) return true;
	}
	return false;
}

int dfs(int v, int ojc, const string& s) {
	int wyn = 1;
	for (int i = 0; i < tab[v].size(); i++) {
		int u = tab[v][i];
		if (u != ojc) {
			wyn += dfs(u, v, s);
			if (s[u - 1] == s[v - 1]) wyn--;
		}
	}
	//cerr<<"v = "<<v<<" wyn = "<<wyn<<endl;
	return wyn;
}

int main() {
	int t;
	cin>>t;
	//cerr<<"t = "<<t<<endl;
	
	for (int l = 0; l < t; l++) {
		int n;
		cin>>n;
		//cerr<<"n = "<<n<<endl;
		
		string s1, s2;
		cin>>s1>>s2;
		
		//cerr<<"s1 = "<<s1<<"\ns2 = "<<s2<<endl;

		for (int i = 1; i <= n; i++) {
			tab[i].clear();
		}
		int maxdeg = 0;
		for (int i = 1; i < n; i++) {
			int a, b;
			cin>>a>>b;
			//cerr<<"a = "<<a<<" b = "<<b<<endl;
			tab[a].push_back(b);
			tab[b].push_back(a);
			maxdeg = max(maxdeg, (int)tab[a].size());
			maxdeg = max(maxdeg, (int)tab[b].size());
			//cerr<<"maxdeg = "<<maxdeg<<" "<<tab[a].size()<<" "<<tab[b].size()<<endl;
		}
		/*
		cout<<"wypisuje graf n = "<<n<<endl;
		for (int i = 1; i <= n; i++) {
			cout<<i<<": ";
			for (int j = 0; j < tab[i].size(); j++) {
				cout<<tab[i][j]<<" ";
			}
			cout<<endl;
		}*/
			
		if (zawiera(s2, kol(s1))) { // je�li s1 jednokolorowe i s2 zawiera kolor niewyst�puj�cy w s1
			//cerr<<"jedkokolorowe\n";
			cout<<"NIE\n";
		}
		else {
			if (maxdeg == 0) {
				if (s1 == s2) cout<<"TAK\n";
				else cout<<"NIE\n";
			}
			else if (maxdeg <= 2) { // sciezka
				//cerr<<"sciezka\n";
				int pocz = -1;
				for (int i = 1; i <= n; i++) {
					if (tab[i].size() == 1) {
						pocz = i;
						break;
					}
				}
				
				string p1, p2; // pocz�tkowa i ko�cowa konfiguracja �cie�ki
				// p2 musi wyst�powa� w p1 jako substring
				
				int pop = pocz;
				int v = tab[pocz][0];
				
				//cerr<<pop<<" -> "<<v;
				
				p1 += s1[pop - 1];
				p2 += s2[pop - 1];
				if (s1[pop - 1] != s1[v - 1]) p1 += s1[v - 1];
				if (s2[pop - 1] != s2[v - 1]) p2 += s2[v - 1];
		
				while (tab[v].size() > 1) {
					int u = tab[v][0] == pop ? tab[v][1] : tab[v][0];
					pop = v;
					v = u;
					if (s1[pop - 1] != s1[v - 1]) p1 += s1[v - 1];
					if (s2[pop - 1] != s2[v - 1]) p2 += s2[v - 1];
					//cerr<<" -> "<<v;
				}
				//cerr<<endl;
				//cerr<<"p1 = "<<p1<<"\np2 = "<<p2<<"\n";
				if (p2.length() <= p1.length() && p1.find(p2) < p1.length())
					cout<<"TAK\n";
				else
					cout<<"NIE\n";
			}
			else {
				cout<<"TAK\n";
			}
		}
	}

}