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
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define pi pair<int, int>
#define vi vector<int>
#define mod 1000000007
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll ksm(ll a, ll b) {if (b == 0) return 1; ll ns = ksm(a, b >> 1); ns = ns * ns % mod; if (b & 1) ns = ns * a % mod; return ns;}
using namespace std;
const int maxn = 100005;
vi eg[maxn];
int n;
int c[2][maxn];
char inp[maxn];
vi a, b;
void dfs(int x, int fa) {
    a.pb(c[0][x]), b.pb(c[1][x]);
    for (auto v : eg[x])
        if (v == fa) continue;
        else dfs(v, x);
}
int main() {  
    // freopen("5c.in", "r", stdin);
    // freopen("dmy.out", "w", stdout);
    int t;
    cin >> t;
    for (int cs = 1; cs <= t; cs++) {
        cin >> n;
        for (int i = 0; i < 2; i++) {
            scanf("%s", inp + 1);
            for (int j = 1; j <= n; j++)
                c[i][j] = inp[j] - '0';
        }
        for (int i = 1; i <= n; i++)
            eg[i].clear();
        for (int i = 1; i < n; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            eg[u].pb(v), eg[v].pb(u);
        }
        int flag = 1;
        int db = 1;
        for (int i = 1; i <= n; i++)
            for (auto v : eg[i])
                if (c[1][i] == c[1][v]) db = 0;
        if (db) 
            for (int i = 1; i <= n; i++)
                if (c[0][i] != c[1][i]) flag = 0;
        int fl[2][2] = {0};
        for (int i = 1; i <= n; i++)
            fl[0][c[0][i]] = 1, 
            fl[1][c[1][i]] = 1;
        for (int i = 0; i < 2; i++)
            if (fl[1][i] && !fl[0][i]) flag = 0;
        a.clear(), b.clear();
        int ln = 1;
        for (int i = 1; i <= n; i++)
            if (eg[i].size() > 2) ln = 0;
        if (ln) {
            for (int i = 1; i <= n; i++) 
                if (eg[i].size() < 2) {
                    dfs(i, 0);
                    break;
                }
            int p = 0;
            for (int i = 0; i < b.size(); i++) {
                if (i && b[i] == b[i - 1]) continue;
                while (p < a.size() && a[p] != b[i]) p += 1;
            }
            if (p == a.size()) flag = 0;
        }
        if (flag) printf("TAK\n");
        else printf("NIE\n");
    }
    return (0-0); // <3 cxr
}
/*
5
1 2
1 1
1 4
1 5
1 1*/