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 <bits/stdc++.h>
#define int long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int MAX=1e5+5;
char color1[MAX];
char color2[MAX];
int gle[MAX];
vi P[MAX];
int n;
int sciezka(){
  int root=-1;
	for (int i=1;i<=n;i++){
		if (sz(P[i])==1)root=i;
		else if (sz(P[i])>2){
			return -1;
		}
	}
	return root;
}
string func(int root,bool flaga){
	int fa=-1;
	string ans="";
	while (true){
	  if (!flaga){
			char lit=color1[root];
			if (ans.empty() || lit!=ans.back())ans.pb(lit);
	  }	
	  else{
			char lit=color2[root];
			if (ans.empty() || lit!=ans.back())ans.pb(lit);
	  }
	  int prv=root;
	  for (auto it:P[root])if (it!=fa)root=it;
	  fa=prv;
	  if (root==prv)break;
	}
	return ans;
}

vi v1,v2;

void dfs(int u,int fa){
	if (gle[u]%2==0)v1.pb(u);
	else v2.pb(u);
	for (auto it:P[u]){
		if (it==fa)continue;
		gle[it]=gle[u]+1;
		dfs(it,u);
	}
}
void solve(){
  v1.clear(),v2.clear();
	cin>>n;
	for (int i=1;i<=n;i++)cin>>color1[i];
	for (int i=1;i<=n;i++)cin>>color2[i],P[i].clear();
	for (int i=1;i<=n-1;i++){
		int a,b;
		cin>>a>>b;
		P[a].pb(b);
		P[b].pb(a);
	}
	
	if (sciezka()!=-1){
	  int root=sciezka();
		string s1=func(root,0);
		string s2=func(root,1);
		int x=sz(s1),y=sz(s2);
		//cout<<"LEN "<<sz(s1)<<" "<<sz(s2)<<" "<<s1<<" "<<s2<<"\n";
		if (s1[0]!=s2[0])x--;
		if (x>=y)cout<<"TAK\n";
		else cout<<"NIE\n";
		return;
	}
	
	bool allb1=true,allr1=true,allb2=true,allr2=true;
	for (int i=1;i<=n;i++){
		if (color1[i]!='0')allb1=false;
		if (color1[i]!='1')allr1=false;
		if (color2[i]!='0')allb2=false;
		if (color2[i]!='1')allr2=false;
	}	
	if ((allb1 && !allb2)){cout<<"NIE\n";return;}
	if ((allr1 && !allr2)){cout<<"NIE\n";return;}
	if ((allb1 && allb2)){cout<<"TAK\n";return;}
	if ((allr1 && allr2)){cout<<"TAK\n";return;}
	
	gle[1]=0;
	dfs(1,-1);
	bool d1a=true,d1b=true,d2a=true,d2b=true;
	// kolorowanie1 0-1 kolorowanie2 0-2
	for (auto it:v1){
		if (color1[it]!='0')d1a=false;
		if (color2[it]!='0')d2a=false;
		if (color1[it]!='1')d1b=false;
		if (color2[it]!='1')d2b=false;
	}
	for (auto it:v2){
		if (color1[it]!='1')d1a=false;
		if (color2[it]!='1')d2a=false;
		if (color1[it]!='0')d1b=false;
		if (color2[it]!='0')d2b=false;
	}
	if (d1a && d2b){cout<<"NIE\n";return;}
	if (d1b && d2a){cout<<"NIE\n";return;}
	if ((!d1a && !d1b) && (d2a || d2b)){cout<<"NIE\n";return;}
	cout<<"TAK\n";
}
int32_t main(){
  BOOST;
  int t;
  cin>>t;
  for (int z=0;z<t;z++){
		solve();
  }
  return 0; 
}