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
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<b;++i)
#define FORD(i,a,b) for(int i=a;i>=b;--i)
#define PB push_back
#define EB emplace_back
#define FI first
#define SE second
#define umap unordered_map
#define uset unordered_set
#define vi vector<int>
#define vvi vector<vi>
#define vll vector<ll>
#define vvll vector<vll>
#define vpii vector<pii>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ALL(X) (X).begin(),(X).end()
#ifndef DEBUG
#define endl (char)10
#endif
using namespace std;
using ll = long long;
using ld = long double;

template <class T>
istream& operator>> (istream& is, vector<T>& vec){
    FOR(i,0,vec.size()) is >> vec[i];
    return is;
}
template <class T>
ostream& operator<< (ostream& os, vector<T>& vec){
    for(auto& t : vec) os << t << " ";
    return os;
}

void st() {
    int n;
    string s, t;
    cin >> n >> s >> t;
    bool suk = (s == t);
    vvi V(n);
    FOR(i,1,n){
        int a, b;
        cin >> a >> b;
        a--; b--;
        V[a].PB(b);
        V[b].PB(a);
    }
    vi cnt(2, 0);
    FOR(i,0,n) cnt[s[i] - '0']++;
    if (cnt[0] == 0 || cnt[1] == 0){
        cout << (suk ? "TAK" : "NIE") << endl;
        return;
    }
    vi scnt(2);
    FOR(i,0,n){
        if (V[i].size() >= 3){
            scnt[0] = scnt[1] = 0;
            for(int x : V[i]) scnt[t[x] - '0']++;
            if (scnt[0] != 0 && scnt[1] != 0) suk = true;
            else if (scnt[t[i] - '0'] != 0) suk = true;
        }
    }
    vi karakany;
    bool suk2 = true;
    FOR(i,0,n){
        if (V[i].size() < 3) karakany.PB(i);
        else if (s[i] != t[i]) suk2 = false;
    }
    vvi G(karakany.size());
    FOR(i,0,karakany.size()){
        for(int x : V[karakany[i]]){
            auto it = lower_bound(ALL(karakany), x);
            if (it != karakany.end() && *it == x){
                G[i].PB(it - karakany.begin());
            }
        }
    }
    vi vis(karakany.size(), 0);
    FOR(i,0,karakany.size()){
        if (vis[i] != 0 || G[i].size() > 1) continue;
        vis[i] = 1;
        if (G[i].size() == 0){
            if (s[karakany[i]] != t[karakany[i]]) suk2 = false;
        } else {
            vi sciezka;
            int prv = -1;
            int v = i;
            sciezka.PB(karakany[i]);
            while(true){
                if (G[v].size() == 1 && G[v][0] == prv) break;
                if (G[v][0] != prv){
                    prv = v;
                    v = G[v][0];
                } else {
                    prv = v;
                    v = G[v][1];
                }
                vis[v] = 1;
                sciezka.PB(karakany[v]);
            }
            int pasu = 0;
            FOR(x,0,sciezka.size()){
                while(pasu < sciezka.size() && s[sciezka[pasu]] != t[sciezka[x]]) pasu++;
                if (pasu == sciezka.size()) break;
            }
            if (pasu == sciezka.size()) suk2 = false;
        }
    }
    suk |= suk2;
    cout << (suk ? "TAK" : "NIE") << endl;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    FOR(i,0,t){
        if (t < 50){
            cerr << "-------------------" << endl;
        }
        //cout << "Case #" << i + 1 <<": ";
        st();
    }
}