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
129
130
131
132
133
134
#include <iostream>
#include <vector>
#include <utility>

typedef std::vector<int> vi;

const int N = 100005;
int q;
int n;
std::string c1;
std::string c2;
vi edges[N];

void input() {
    std::cin >> n;
    std::cin >> c1 >> c2;
    int u, v;
    for (int i = 0; i < n; i++) {
        edges[i].clear();
    }
    for (int i = 0; i < n - 1; i++) {
        std::cin >> u >> v;
        u--;
        v--;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
}

int max(int a, int b) {
    return a > b ? a : b;
}

bool is_line() {
    for (int i = 0; i < n; i++) {
        if (edges[i].size() > 2) {
            return false;
        }
    }
    return true;
}

bool same() {
    return c1 == c2;
}

bool is_correct_line() {
    int u = 0;
    for (int i = 0; i < n; i++) {
        if (edges[i].size() == 1) {
            u = i;
            break;
        }
    }
    std::string s1 = "", s2 = "";
    s1 += c1[u];
    s2 += c2[u];
    // std::cout << s1 << " " << s2 << "\n";
    int v = (u == edges[u][0] ? edges[u][1] : edges[u][0]);
    // std::cout << "u " << u << " v " << v << "\n";
    while (edges[v].size() > 1) {
        int v2 = (u == edges[v][0] ? edges[v][1] : edges[v][0]);
        u = v;
        v = v2;

        if (c1[u] != s1[s1.length() - 1]) {
            s1 += c1[u];
        }
        if (c2[u] != s2[s2.length() - 1]) {
            s2 += c2[u];
        }
        // std::cout << s1 << " " << s2 << "\n";
        // std::cout << "u " << u << " v " << v << "\n";
    }

    if (c1[v] != s1[s1.length() - 1]) {
        s1 += c1[v];
    }
    if (c2[v] != s2[s2.length() - 1]) {
        s2 += c2[v];
    }

    // std::cout << s1 << " " << s2 << "\n";

    return s1.find(s2) != std::string::npos;
}

bool has_both_colors(std::string & s) {
    return s.find('0') != std::string::npos && s.find('1') != std::string::npos;
}

bool neightbour_same_color() {
    for (int u = 0; u < n; u++) {
        for (auto v : edges[u]) {
            if (c2[u] == c2[v]) {
                return true;
            }
        }
    }
    return false;
}

bool solve() {
    // std::cout << q << "\n";
    if (same()) {
        return true;
    }

    if (!has_both_colors(c1)) {
        return false;
    }

    if (!neightbour_same_color()) {
        return false;
    }

    if (!is_line()) {
        //  std::cout << " is not line\n";
        return true;
    }

    return is_correct_line();
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cin >> q;
    while (q--) {
        input();
        std::cout << (solve() ? "TAK\n" : "NIE\n");
    }
    return 0;
}