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
128
129
130
131
#include<bits/stdc++.h>

#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vii vector<pii>
#define vb vector<bool>
#define vvb vector<vb>
#define vl vector<ll>
#define endl '\n'
#define turbo ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back
#define ll long long
#define f first
#define s second

using namespace std;

vvi v;
string s1, s2;
int n;

bool spychacz(int e, int p, bool spych)
{
    vi t(2, 0);
    for(auto it : v[e])
        if(it != p)
            t[s2[it-1]-'0']++;
    if((spych and t[1]) or (!spych and t[0]))
        return true;
    for(auto it : v[e])
        if(it != p)
            return spychacz(it, e, !spych);
    return false; 
}

pii napierdalaj_dp(int e, int p, int ile1 = 0, int ile2 = 0)
{
    if(s1[e-1] != s1[p-1])
        ile1++;
    if(s2[e-1] != s2[p-1])
        ile2++;
    for(auto it : v[e])
        if(it != p)
            return napierdalaj_dp(it, e, ile1, ile2);
    return {ile1, ile2};
}

bool go_dp()
{
    for(int e = 1; e <= n; e++)
        if(v[e].size() <= 1)
        {
            auto it = napierdalaj_dp(e, e);
            if(it.f == it.s)
                return s1[e-1] == s2[e-1];
            return it.f > it.s;
        }
        
    return false;
}

int main()
{
    turbo
    int q; cin >> q;
    while(q--)
    {
        cin >> n >> s1 >> s2;
        v = vvi(n+10);
        vi t1(2, 0), t2(2, 0);
        for(auto it : s1)
            t1[it-'0']++;
        for(auto it : s2)
            t2[it-'0']++;
        for(int i = 0; i < n-1; i++)
        {
            int a, b; cin >> a >> b;
            v[a].pb(b);
            v[b].pb(a);
        }
        if((!t1[0] and t2[0]) or (!t1[1] and t2[1]))
        {
            cout << "NIE\n";
            continue;
        }
        if(s1 == s2)
        {
            cout << "TAK\n";
            continue;
        }
        int ile_ancymonkow = 0;
        bool senko = false;
        for(int e = 1; e <= n; e++)
            if(v[e].size() >= 3)
            {
                ile_ancymonkow++;
                int murzyn = 0;
                for(auto it : v[e])
                    if(s2[it-1] == '1')
                        murzyn++;
                if(murzyn != v[e].size() and murzyn)
                {
                    senko = true;
                    break;
                }
                if((murzyn == v[e].size() and s2[e-1] == '1') or (!murzyn and s2[e-1] == '0'))
                {
                    senko = true;
                    break;
                }
            }
        if(senko)
        {
            cout << "TAK\n";
            continue;
        }
        if(!ile_ancymonkow)
        {
            cout << (go_dp() ? "TAK\n" : "NIE\n");
            continue;
        }
        for(int e = 1; e <= n; e++)
            if(v[e].size() >= 3)
                for(auto it : v[e])
                    if(spychacz(it, e, !(s2[e-1]-'0')))
                        senko = true;
        cout << (senko ? "TAK\n" : "NIE\n");
    }
}