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
#define make_pair mp
#define emplace_back pb
#include <bits/stdc++.h>
using namespace std;
mt19937 mt_rand(time(0));
const int N = 1e5 + 5;
int n, t, perm[N];
vector<int> v[N];
bool init[N], dest[N];
char s[N];

int main() {
	scanf("%d", &t);
    while(t--) {
        for(int i=1;i<=n;i++) v[i].clear();
        scanf("%d", &n);
        scanf("%s", s);
        for(int i=0;i<n;i++) init[i+1] = s[i] - '0';
        scanf("%s", s);
        for(int i=0;i<n;i++) dest[i+1] = s[i] - '0';
        
        for(int i=1;i<n;i++) {
            int a, b;
            scanf("%d%d", &a, &b);
            v[a].pb(b);
            v[b].pb(a);
        }

        int cnt = 0;
        for(int i=1;i<=n;i++) cnt += init[i];

        if(cnt == 0 || cnt == n) {
            int cnt2 = 0;
            for(int i=1;i<=n;i++) cnt2 += dest[i];
            if(cnt == cnt2) printf("TAK\n");
            else printf("NIE\n");
            continue;
        }

        int maks = 0;
        for(int i=1;i<=n;i++) maks = max(maks, (int)v[i].size());
        if(maks > 2) {
            bool ok = true;
            for(int i=1;i<=n;i++)
            for(auto x : v[i]) if(dest[i] == dest[x]) ok = false;

            if(!ok) {
                printf("TAK\n");
                continue;
            }

            ok = true;
            for(int i=1;i<=n;i++) if(init[i] != dest[i]) {
                printf("NIE\n");
                ok = false;
                break;
            } 
            if(ok) printf("TAK\n");
            continue;
        }

        int root = 1;
        while(v[root].size() == 2) root++;
        perm[1] = root;
        for(int i=2;i<=n;i++) {
            int prev = perm[i-1];
            int prev2 = perm[i-2];
            for(auto x : v[prev]) if(x != prev2) {
                perm[i] = x;
                break;
            }
        }
        cnt = 0;
        int cnt2 = 0;
        perm[n+1] = 0;
        for(int i=1;i<=n+1;i++) if(init[perm[i]] == 0 && init[perm[i-1]] == 1) cnt++;
        for(int i=1;i<=n+1;i++) if(dest[perm[i]] == 0 && dest[perm[i-1]] == 1) cnt2++;
        if(init[perm[1]] == 1 && dest[perm[1]] == 0) cnt--;
        if(init[perm[n]] == 1 && dest[perm[n]] == 0) cnt--;


        if(cnt >= cnt2) printf("TAK\n");
        else printf("NIE\n");
    }
	return 0;
}