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
#include<cstdio>
#include<algorithm>
#include<vector>
#include<iostream>
#define S 100007
using namespace std;

string s,s2;

vector < int > V[S];
vector < int > P;
int main(void){
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        cin >> s >> s2;
        int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
        for(int i = 0; i < s.size();i++){
            if(s[i] == '0'){
                x1++;
            }else{
                y1++;
            }
        }
        for(int i = 0; i < s2.size();i++){
            if(s2[i] == '0'){
                x2++;
            }else{
                y2++;
            }
        }
        bool zle = false;
        if( (x1 == 0 && x2 != 0) || (y1 == 0 && y2 != 0) ){
            zle = true;
        }
        int a,b;
        for(int i = 1; i <= n-1;i++){
            scanf("%d %d",&a,&b);
            V[a].push_back(b);
            V[b].push_back(a);
        }
        int st = 0;
        for(int i = 1; i <= n;i++){
            st = max(st,(int)V[i].size());
        }
        int start = 0;
        if(st <= 2 && n > 1){
            for(int i = 1; i <= n;i++){
                if(V[i].size() == 1){
                    start = i;
                }
            }
            int b = V[start][0];
            int prev = start;
            P.push_back(start);
            while(1){
                P.push_back(b);
                if(V[b].size() == 1)
                    break;
                if(V[b][0] != prev){
                    prev = b;
                    b = V[b][0];
                }else{
                    prev = b;
                    b = V[b][1];
                }
            }
            char c = s[P[0]-1];
            int zm = 0;
            for(int i = 1; i < n; i++){
                if(s[P[i]-1] != c){
                    zm++;
                    c = s[P[i]-1];
                }
            }
            c = s2[P[0]-1];
            int zm2 = 0;
            for(int i = 1; i < n; i++){
                if(s2[P[i]-1] != c){
                    zm2++;
                    c = s2[P[i]-1];
                }
            }
            if(s[P[0]-1] != s2[P[0]-1]){
                zm--;
            }
            if(zm2 > zm)
                zle = true;
        }else{
            bool test = false;
            for(int i = 1; i <= n;i++){
                for(int j = 0 ; j < V[i].size();j++){
                    int v = V[i][j];
                    if(s2[i-1] == s2[v-1])
                        test = true;
                }
            }
            if(!test)
                zle = true;
        }
        if(s == s2)
            zle = false;
        if(zle){
            printf("NIE\n");
        }else{
            printf("TAK\n");
        }
        for(int i = 1; i <= n;i++){
            V[i].clear();
        }
        P.clear();
    }

    return 0;
}
/*
1
5
00010
01100
2 1
3 1
4 3
5 3
*/