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
#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
string s1,s2;
int n,q,vis[100010],deg[100010];
vector <int> g[100010];
pair <int,int> max_deg;
bool sciezka(){
    int x = 0;
    for(int i = 0; i < n; i++)
        if(deg[i] == 1)
            x = i;
    vector <int> tab;
    queue <int> o,z;
    tab.push_back(x);
    if(s1[x] == '1')
        o.push(0);
    else
        z.push(0);
    for(int i = 0; i < n - 1; i++){
        x = (!vis[g[x][0]] ? g[x][0] : g[x][1]);
        tab.push_back(x);
        if(s1[x] == '1')
            o.push(i + 1);
        else
            z.push(i + 1);
    }
    int val=0,till=-1,last=2;
    for(int i = 0; i < tab.size(); i++){
        //cout << s1[tab[i]] << " ";
        if(i && s2[tab[i-1]] == s2[tab[i]])
            continue;
        if((till >= i && val != s2[tab[i]]) || (s2[tab[i]] != s1[tab[i]])){
            if(val == 0){
                while(!o.empty() && o.front() < max(till+1,i))
                    o.pop();
                if(o.empty())
                    return false;
                till = o.front();
            }
            else{
                while(!z.empty() && z.front() < max(till+1,i))
                    z.pop();
                if(z.empty())
                    return false;
                till = z.front();
            }
            val = !val;
        }//cout << till << " " << val << endl;
    }
    return true;
    
}
void test_case(){
    cin >> n >> s1 >> s2;
    bool czy = false;
    max_deg = make_pair(0,0);
    for(int i = 0; i < n; i++){
        if(i && s1[i] != s1[i-1])
            czy = true;
        deg[i] = vis[i] = 0;
        g[i].clear();
    }if(!czy){cout << "NIE\n";return;}
    for(int i = 0; i < n - 1; i++){
        int a,b; cin >> a >> b;
        a--,b--;
        g[a].push_back(b);
        g[b].push_back(a);
        deg[a]++; deg[b]++;
        if(max_deg.first < deg[a])
            max_deg = make_pair(deg[a],a);
        if(max_deg.first < deg[b])
            max_deg = make_pair(deg[b],b);
    }
    if(s1 == s2){
        cout << "TAK\n";
        return;
    }
    if(max_deg.first <= 2){
        if(sciezka() == true)
            cout << "TAK\n";
        else
            cout << "NIE\n";
        return;
    }
    for(int i = 0; i < n; i++){
        if(deg[i] > 2){
            for(auto j : g[i]){
                if(s2[i] != s2[j]){
                    cout << "TAK\n";
                    return;
                }
            }
        }
    }
    cout << "NIE\n";
    return;
}
int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> q;
    while(q--)
        test_case();
}