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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n;
vector<int> adj[100009];
bool state[2][100009];
int deg[100009];
int red[2], black[2];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    for(int tt=0; tt<t; tt++) {
        int a,b;
        char c;
        cin >> n;
        for(int k = 0; k < 2; k++) {
            for(int i = 1; i <= n; i++) {
                cin >> c;
                state[k][i] = (c == '1');
                if(state[k][i])
                    black[k]++;
                else
                    red[k]++;
            }
        }
        for(int i = 0; i < n-1; i++) {
            cin >> a >> b;
            adj[a].push_back(b);
            adj[b].push_back(a);
            deg[a]++;
            deg[b]++;
        }
        bool path = true;
        vector<int> leaves;
        for(int i = 1; i <= n; i++) {
            if(deg[i] == 1 and leaves.size() < 2)
                leaves.push_back(i);
            if(deg[i] > 2)
                path = false;
        }
        if(n == 1) {
            if(state[0][1] != state[1][1])
                cout << "NIE\n";
            else
                cout << "TAK\n";
        }
        else {
            if(path) {
                int last = 0, curr = leaves[0];
                string s[2] = {"", ""};
                do {
                    if(last == 0 or state[0][last] != state[0][curr])
                        s[0] += (state[0][curr] ? '1' : '0');
                    if(last == 0 or state[1][last] != state[1][curr])
                        s[1] += (state[1][curr] ? '1' : '0');

                    if(last == 0) {
                        last = curr;
                        curr = adj[curr][0];
                    }
                    else {
                        if(last != adj[curr][0]) {
                            last = curr;
                            curr = adj[curr][0];
                        }
                        else {
                            last = curr;
                            curr = adj[curr][1];
                        }
                    }
                } while(last != leaves[1]);

                if(s[0].length() > s[1].length() or s[0] == s[1])
                    cout << "TAK\n";
                else
                    cout << "NIE\n";
            }
            else {
                if((black[0] == 0 and black[1] > 0) or (red[0] == 0 and red[1] > 0))
                    cout << "NIE\n";
                else
                    cout << "TAK\n";
            }
        }

        for(int i = 0; i <= n+5; i++) {
            adj[i].clear();
            deg[i] = 0;
            state[0][i] = state[1][i] = 0;
        }
        red[0] = red[1] = 0;
        black[0] = black[1] = 0;
    }

    return 0;
}