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>

using namespace std;

void dfs(int c, int p, vector<vector<int>>& graph, string& act, string& need, bool& ok){
    for (auto& child : graph[c]){
        if (child != p){
            if (need[c-1] == need[child-1])
                ok = true;
            dfs(child, c, graph, act, need, ok);
        }
    }
}

void solve(){
    int n;
    cin >> n;
    string act, need;
    cin >> act;
    cin >> need;

    vector<bool> need_is(2), act_is(2);
    for (int i = 0; i < n; i++){
        act_is[act[i] - '0'] = true;
        need_is[need[i] - '0'] = true;
    }

    vector<vector<int>> graph(n+1);
    vector<int> edges(n+1);
    int a, b;
    for (int i = 0; i < n-1; i++){
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
        edges[a]++;
        edges[b]++;
    }

    if (act == need){
        cout << "TAK" << "\n";
        return;
    }

    if ((need_is[0] == true && act_is[0] == false) || (need_is[1] == true && act_is[1] == false)){
        cout << "NIE" << "\n";
        return;
    }

    int curr = -1;
    for (int i = 1; i <= n; i++){
        if (edges[i] == 1)
            curr = i;
        if (edges[i] >= 3){
            int was0 = 0, was1 = 0;
            for (auto& child : graph[i]){
                was0 |= (need[child-1] == '0');
                was1 |= (need[child-1] == '1');
            }
            if ((was0 && was1) || ((was0 && need[i] == 0) || (was1 && need[i] == 1))){
                cout << "TAK" << "\n";
                return;
            }
        }
    }

    for (int i = 1; i <= n; i++){
        if (edges[i] >= 3){
            bool ok = false;
            dfs(i, -1, graph, act, need, ok);
            cout << ((ok) ? "TAK" : "NIE") << "\n";
            return;
        }
    }

    vector<int> tab_a(n), tab_n(n);
    queue<int> ones, zeros;
    vector<bool> seen(n+1);
    for (int i = 0; true; i++){
        tab_a[i] = act[curr-1] - '0';
        tab_n[i] = need[curr-1] - '0';
        if (act[curr-1] == '0')
            zeros.push(i);
        else 
            ones.push(i);
        if (graph[curr].size() == 1 && seen[graph[curr][0]])
            break;
        seen[curr] = true;
        curr = ((seen[graph[curr][0]]) ? graph[curr][1] : graph[curr][0]);
    }

    int all_0 = -1, all_1 = -1;
    for (int i = 0; i < n; i++){
        if (tab_n[i] == 0){
            while (zeros.size() > 0 && all_1 >= zeros.front())
                zeros.pop();
            if (zeros.size() == 0){
                cout << "NIE" << "\n";
                return;
            }

            all_0 = zeros.front();
        }
        else{
            while (ones.size() > 0 && all_0 >= ones.front())
                ones.pop();
            if (ones.size() == 0){
                cout << "NIE" << "\n";
                return;
            }

            all_1 = ones.front();
        }
    }

    cout << "TAK" << "\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while (t){
        solve();
        t--;
    }    
    return 0;
}