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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<vector>
using namespace std;
int t,n,a,b,tab[100005],x1,x2;
string s1,s2,s3,s4;
vector<int> v[100005];
void DFS(int x,int f){
  s3+=s1[x-1];
  s4+=s2[x-1];
  for(auto i:v[x]){
    if(i==f) continue;
    DFS(i,x);
  }
}
int main(){
  ios_base::sync_with_stdio(0);
  cin>>t;
  for(int u=0;u<t;u++){
    cin>>n>>s1>>s2;
    if(n==1){
      if(s1==s2) cout<<"TAK\n"; else cout<<"NIE\n";
      continue;
    }
    for(int i=1;i<=n;i++){
      tab[i]=0; v[i].clear();
    }
    for(int i=1;i<n;i++){
      cin>>a>>b;
      v[a].push_back(b);
      v[b].push_back(a);
      tab[a]++,tab[b]++;
    }
    x1=0,x2=0;
    for(int i=0;i<n;i++) if(s2[i]=='0') x1=1; else x2=1;
    for(int i=0;i<n;i++) if(s1[i]=='0') x1=0; else x2=0;
    if(x1+x2!=0){
      cout<<"NIE\n";
      continue;
    }
    a=-1;
    for(int i=1;i<=n;i++){
      if(tab[i]==1) a=i;
      if(tab[i]>2){
        a=-2; break;
      }
    }
    //cout<<a<<"\n";
    if(a==-2){
      cout<<"TAK\n";
    }else{
      s3=""; s4="";
      DFS(a,-1);
      //cout<<s3<<" "<<s4<<"\n";
      x1=1; x2=1;
      for(int i=1;i<n;i++){
        if(s3[i]!=s3[i-1]) x1++;
        if(s4[i]!=s4[i-1]) x2++;
      }
      if(s3[0]!=s4[0]) x1--;
      if(s3[n-1]!=s4[n-1]) x1--;
      if(x1>=x2) cout<<"TAK\n"; else cout<<"NIE\n";
    }
  }
  return 0;
}