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
#include <cstdio>
#include <vector>

using namespace std;
#define MAX 200000

#define D(x)

char c1[MAX];
char c2[MAX];
int t,n,a,b;
int V[MAX];
vector<int> E[MAX];

int next(int &x, int &y) {
    int z = 0;
    for(int i : E[y]) {
        if(i != x) {
            z = i;
            break;
        }
    }
    x = y;
    y = z;
    return z;
}

int main() {
    scanf("%d", &t);
    while(t--) {
        int r = 1, neighboring_same = 0;
        scanf("%d %s %s", &n, c1, c2);
        for(int i=0;i<=n;i++) V[i] = 0;
        for(int i=0;i<=n;i++) E[i].clear();

        for(int i=1;i<n;i++) {
            scanf("%d %d", &a, &b);
            V[a]++;
            V[b]++;
            E[a].push_back(b);
            E[b].push_back(a);
            if(c2[a-1] == c2[b-1]) neighboring_same++;
        }
        int eq = 1;
        for(int i=0;i<n && eq;i++) if(c1[i] != c2[i]) eq = 0;
        D(printf("eq: %d\n",eq));

        if(!eq) {
            int col1=0, col2=0;
            for(int i=0;i<n;i++) if(c1[i] == '1') col1++;
            for(int i=0;i<n;i++) if(c2[i] == '1') col2++;
            if (col1 == n || col1 == 0) r = 0;
            D(printf("r: %d col1:%d col2: %d\n",r, col1, col2));


            if(r) {
                int E3=0,ie3;
                for(ie3=1;ie3<=n;ie3++) {
                    if (V[ie3]>2) {
                        E3 = 1;
                        break;
                    }
                }
                D(printf("r: %d E3:%d ie3:%d\n",r,E3, ie3));


                if(E3 == 0) {
                    int V1=0;
                    for(int i=1;i<=n && V1 == 0;i++) if (V[i]==1) V1 = i;
                    int chg1=0,chg2=0;

                    int x = 0, y = V1; 
                    for(int i=1;i<n;i++) if(c1[y-1] != c1[next(x, y) - 1]) chg1++;
                    x = 0, y = V1; 
                    for(int i=1;i<n;i++) if(c2[y-1] != c2[next(x, y) - 1]) chg2++;
                    if(chg1<chg2) {
                        r = 0;
                    } else if(chg1 == chg2) {
                        if (c1[V1-1] != c2[V1-1]) r = 0;
                    }
                } else {
                    if (!neighboring_same) r = 0;
                    D(printf("r: %d neig:%d\n",neighboring_same));

                }
            }
        }

        if (r)  printf("TAK\n");
        else    printf("NIE\n");
    }
}