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
#include <cstdio>
#include <vector>
#include <set>
using namespace std;

#define FOR(i,a,b) for(int (i)=(int)(a); (i)!=(int)(b); ++(i))

struct Node {
    char src, dst;
    vector<Node*> adj;
};

int t, n;
char S[100005];
vector<Node> nodes;

bool solve() {

    // Read input
    scanf("%d", &n);
    nodes.resize(n);
    scanf("%s", S); FOR(i,0,n) nodes[i].src = S[i];
    scanf("%s", S); FOR(i,0,n) nodes[i].dst = S[i];
    FOR(i,0,n-1) {
        int a, b;
        scanf("%d %d", &a, &b); --a; --b;
        nodes[a].adj.push_back(&nodes[b]);
        nodes[b].adj.push_back(&nodes[a]);
    }

    // Analyse
    Node *v1 = 0;
    int max_d = 0;
    bool changed = false;
    bool dst_has_adj_with_one_color = false;
    bool good_hub_exists = false;
    bool src_0 = false, src_1 = false, dst_0 = false, dst_1 = false;
    FOR(i,0,n) {
        Node &node = nodes[i];
        max_d = max(max_d, (int)(node.adj.size()));
        if (node.adj.size() == 1 && v1 == 0) v1 = &node;
        if (node.src != node.dst) changed = true;
        if (node.src == '0') src_0 = true; else src_1 = true;
        if (node.dst == '0') dst_0 = true; else dst_1 = true;
        bool adj_0 = false, adj_1 = false;
        FOR(j,0,node.adj.size()) {
            Node &adj_node = *node.adj[j];
            if (adj_node.dst == node.dst) dst_has_adj_with_one_color = true;
            if (adj_node.dst == '0') adj_0 = true; else adj_1 = true;
        }
        if (node.adj.size() >= 3) {
            if (adj_0 && adj_1) good_hub_exists = true;
            else if (adj_0 && node.dst == '0') good_hub_exists = true;
            else if (adj_1 && node.dst == '1') good_hub_exists = true;
        }
    }

    // Case 1 - no changes
    if (!changed) return true;

    // Case 2 - dst has color which does not exist inside src
    if (!src_0) return !dst_0;
    if (!src_1) return !dst_1;

    // Case 3 - dst has only one color which exists inside src
    if (!dst_1) return src_0;
    if (!dst_0) return src_1;

    // Case 4 - tree is a path
    if (max_d <= 2) {
        vector<char> src_bin, dst_bin;
        Node *prev = 0;
        Node *node = v1;
        while(true) {
            if (src_bin.empty() || src_bin.back() != node->src) src_bin.push_back(node->src);
            if (dst_bin.empty() || dst_bin.back() != node->dst) dst_bin.push_back(node->dst);
            if (node->adj.size() == 1 && prev != 0) break;
            Node *next = node->adj[0];
            if (next == prev) next = node->adj[1];
            prev = node;
            node = next;
        }

        if (src_bin.size() > dst_bin.size()) return true;
        if (src_bin.size() < dst_bin.size()) return false;
        return src_bin[0] == dst_bin[0];
    }

    // Case 5 - There is a "hub" which can be used to modify exerything
    if (good_hub_exists) return true;
    if (dst_has_adj_with_one_color) return true;

    return false;
}


int main() {
    scanf("%d", &t);
    while (t--) {
        nodes.clear();
        bool result = solve();
        if (result) printf("TAK\n"); else printf("NIE\n");
    }
}