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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifdef LOCAL
#define debug(...) __VA_ARGS__
#else
#define debug(...) {}
#endif
vector<int> sas[100001];
bool vis[100001];
string s1,s2;
int n;
bool DFS(int v){
    vis[v] = 1;
    bool good = (s1[v-1] == s2[v-1]);
    for (int u : sas[v]){
        cout<<v<<" "<<s2[v-1]<<" # "<<u<<" "<<s2[u-1]<<"\n";
        if (vis[u] || s2[u-1] != s2[v-1]) continue;
        good |= DFS(u);
    }
    return good;
}
void DFS2(int v){
    vis[v] = 1;
    for (int u = 1; u < n+1; u++){
        for (int z : sas[u]){
            if (bool(v&(1<<u)) != bool(v&(1<<z))){
                //cout<<v<<" -> "<<(v^(1<<u))<<"\n";
                //cout<<v<<" -> "<<(v^(1<<z))<<"\n";
                if (!vis[v^(1<<u)]) DFS2(v^(1<<u));
                if (!vis[v^(1<<z)]) DFS2(v^(1<<z));
            }
        }    
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int i;
    int t;
    cin>>t;
    while (t--){
        cin>>n;
		cin>>s1>>s2;
        int maxdeg = 0;
        for (i = 1; i < n+1; i++){
            vis[i] = 0;
            sas[i].clear();
        }
        bool czya = 0;
        bool czyb = 0;
        for (char c : s1){
            if (c == '0') czya = 1;
            else czyb = 1;
        }
        for (i = 0; i < n-1; i++){
            int a,b;
            cin>>a>>b;
            sas[a].push_back(b);
            sas[b].push_back(a);
            maxdeg = max({maxdeg,int(sas[a].size()),int(sas[b].size())});
        }
        if (s1 == s2){
            cout<<"TAK\n";
            continue;
        }
        if (!czya || !czyb){
            cout<<"NIE\n";
            continue;
        }
        if (maxdeg < 3){
            bool good = 0;
            for (i = 0; i < n ; i++) if (s1[i] == s2[i]) good = 1;
            if (!good){
                cout<<"NIE\n";
                continue;
            }
            int sus = 0;
            int sus2 = 0;
            bool ok = 1;
            for (i = 1; i < n+1; i++){
                for (int j : sas[i]) if (s1[i-1] != s1[j-1]) sus++;
                if (sas[i].size() == 1){
                    if (s1[i-1] != s2[i-1]) ok = 0;
                }
            }
            for (i = 1; i < n+1; i++) for (int j : sas[i]) if (s2[i-1] != s2[j-1]) sus2++;
            if (sus < sus2) cout<<"NIE\n";
            if (sus > sus2) cout<<"TAK\n";
            if (sus == sus2){
                if (ok) cout<<"TAK\n";
                else cout<<"NIE\n";
            }
        }else{
            bool good = 0;
            for (i = 1; i < n+1; i++) for (int j : sas[i]) if (s2[i-1] == s2[j-1]) good = 1; 
            if (good) cout<<"TAK\n";
            else cout<<"NIE\n";
        }
    }
    return 0;
}