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 <algorithm>
#define MAX_N 100010
using namespace std;

char from[MAX_N], to[MAX_N];
vector<int> v[MAX_N];
int n, T, v1, v2;

bool testLine(int leaf) {
    int prev = -1;
    int w = leaf;
    int sFrom = 0;
    int sTo = 0;

    //printf("WTF?\n");

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < (int)v[w].size(); j++) {
            if (v[w][j] != prev) {
                prev = w;
                w = v[w][j];
                break;
            }
        }

        if (from[prev] != from[w]) sFrom++;
        if (to[prev] != to[w]) sTo++;
    }

    //printf("- %d %d\n", sFrom, sTo);

    if (sFrom > sTo) return true;
    if (sFrom < sTo) return false;

    //printf("OOOK\n");
    return from[leaf] == to[leaf];
}

bool test(int no) {
    int r = 0, b = 0;
    int rt = 0, bt = 0;

    scanf("%d", &n);
    scanf("%s", from + 1);
    scanf("%s", to + 1);

    for (int i = 1; i <= n; i++) {
        if (from[i] == '0') r++;
        else b++;

        if (to[i] == '0') rt++;
        else bt++;
    }

    for (int i = 1; i <= n; i++) {
        v[i].clear();
    }

    bool isBipartite = true;
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &v1, &v2);
        v[v1].push_back(v2);
        v[v2].push_back(v1);
        if (to[v1] == to[v2]) isBipartite = false;
    }

    int maxS = 0;
    int leaf = 0;
    for (int i = 1; i <= n; i++) {
        if (v[i].size() == 1) leaf = i;
        maxS = max(maxS, (int)v[i].size());
    }

    if (r == 0) {
        return rt == 0;
    }

    if (b == 0) {
        return bt == 0;
    }

    if (!isBipartite && maxS > 2) {
        return true;
    }

    if (maxS > 2) {
        for (int i = 1; i <= n; i++) {
            if (from[i] != to[i]) return false;
        }
        return true;
    } else {
        return testLine(leaf);
    }
}

int main() {
    scanf("%d", &T);
    for (int i = 0; i < T; i++) {
        if (test(i + 1)) printf("TAK\n");
        else printf("NIE\n");
    }
}