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

int main() {
    int T;
    cin>>T;
    for(int t=0; t<T; ++t) {
        int N;
        cin>>N;
        string P,K;
        cin>>P>>K;
        vector< vector<int> > ls;
        vector<int> V;
        for(int i=0; i<N; ++i) ls.push_back(V);
        bool czN = true;
        int A,B;
        for(int i=0; i<N-1; ++i) {
            cin>>A>>B;
            A--; B--;
            ls[A].push_back(B);
            ls[B].push_back(A);
            if(K[A] == K[B]) {
                czN = false; 
            }
        }
        bool czR = true;
        for(int i=0; i<N; ++i) if(P[i] != K[i]) czR = false;
        if(czR) {
            cout<<"TAK"<<endl;
            continue;
        }
        bool cz1 = true, cz0 = true;
        for(int i=0; i<N; ++i) {
            if(P[i] != '1') cz1 = false;
            if(P[i] != '0') cz0 = false;
        }
        if(cz1 || cz0) {
            cout<<"NIE"<<endl;
            continue;
        }
        if(czN) {
            cout<<"NIE"<<endl;
            continue;
        }
        bool d = false;
        for(int i=0; i<N; ++i) {
            if(ls[i].size() >= 3) {
                d = true;
            }
        }
        if(d) {
            cout<<"TAK"<<endl;
            continue;
        }
        int p = -1, k = -1;
        for(int i=0; i<N; ++i){
            if(ls[i].size() == 1 && p == -1) p = i;
            else if(ls[i].size() == 1) k = i;
        }
        int lP = 0, lK = 0, b = p, pb;
        while(b != k) {
            if(ls[b].size() == 1) {
                int n;
                n = ls[b][0];
                if(P[b] != P[n]) lP++;
                if(K[b] != K[n]) lK++;
                pb = b;
                b = n;
            }
            else {
                int n;
                if(ls[b][0] != pb) n = ls[b][0];
                else n = ls[b][1];
                if(P[b] != P[n]) lP++;
                if(K[b] != K[n]) lK++;
                pb = b;
                b = n;
            }
        }
        if(lP > lK) {
            cout<<"TAK"<<endl;
            continue;
        }
        else if(lP < lK) {
            cout<<"NIE"<<endl;
            continue;
        }
        else {
            if(P[p] == K[p]) cout<<"TAK"<<endl;
            else cout<<"NIE"<<endl;
        }
    }
    
    
    return 0;
}