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
#include <bits/stdc++.h>
using namespace std;

bool podslowo(string &duze, string &male)
{
    return (duze.find(male) != string::npos);
}

bool test()
{
    int n;
    string pocz, kon;
    cin >> n >> pocz >> kon;
    vector<int> graf[n];
    int w1, w2;
    
    for(int i = 0; i < n - 1; i++)
    {
        cin >> w1 >> w2;
        w1--; w2--;
        graf[w1].push_back(w2);
        graf[w2].push_back(w1);
    }
    if(pocz == kon)
        return true;
    int odnogi = 0;
    int samotna = 0;

    for(int i = 0; i < n; i++)
    {
        if(graf[i].size() == 1)
        {
            odnogi++;
            samotna = i;
        }
    }

    //nie sciezka
    if(odnogi > 2)
    {
        int pz = 0, pj = 0, kz = 0, kj = 0;

        for(auto z : pocz)
            if(z == '0')
                pz++;
            else
                pj++;
        
        for(auto z : kon)
            if(z == '0')
                kz++;
            else
                kj++;

        //czerwnono czarne
        bool tak = true;
        for(int i = 0; i < n; i++)
            for(auto s : graf[i])
                if(kon[s] == kon[i])
                {
                    tak = false;
                    i = n;
                    break;
                }
        if(tak) return false;

        if(kz == n and pz > 0)
            return true;
        if(kj == n and pj > 0)
            return true;
        if(pz > 0 and pj > 0)
            return true;
        return false;
    }

    //sciezka
    string sp, sk;
    int next = 3;
    while(next != -1)
    {
        if(pocz[samotna] != sp.back())
            sp += pocz[samotna];
        if(kon[samotna] != sk.back())
            sk += kon[samotna]; 

        next = -1;
        if(graf[samotna].size() > 0 and graf[graf[samotna][0]].size() > 0)
        {
            next = graf[samotna][0];
            graf[samotna].clear();
        }
        else if(graf[samotna].size() > 1 and graf[graf[samotna][1]].size() > 0)
        {
            next = graf[samotna][1];
            graf[samotna].clear();
        }
        samotna = next;
    }

    if(podslowo(sp, sk))
        return true;
    else
        return false;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t; cin >> t;
    while(t--)
        if(test())
            cout << "TAK\n";
        else
            cout << "NIE\n";
}