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
132
133
134
135
136
137
138
139
140
#include <iostream>
#include <vector>
#include <cstdint>


using namespace std;

void wczytajDane(vector<int8_t>& stanPocz, vector<int8_t>& stanKon, vector<vector<uint32_t>>& polaczenia)
{
    uint32_t n=stanPocz.size();
    for (uint32_t ii=0; ii<2*n; ii++)
    {
        char c;
        cin>>c;
        if (ii<n)
            stanPocz[ii] = c-'0';
        else
            stanKon[ii-n] = c-'0';
    }
    for (uint32_t ii=0; ii<n-1; ii++)
    {
        uint32_t a,b; // numery wierzcholkow z przedzialu [1,n]
        cin>>a>>b;
        a--;b--;
        polaczenia[a].push_back(b);
        polaczenia[b].push_back(a);
    }
}

bool czyIdentyczne(const vector<int8_t>& v1, const vector<int8_t>& v2)
{
    for (uint32_t ii=0; ii<v1.size(); ii++)
        if(v1[ii]!=v2[ii])
            return false;
    return true;
}

bool czyDwaKolory(const vector<int8_t>& v1)
{
    if(v1.size()==1)
        return false;
    for (uint32_t ii=1; ii<v1.size(); ii++)
        if(v1[ii] != v1[0])
            return true;
    return false;
}

uint32_t zliczPrzedzialy(const vector<uint32_t>& zakonczenia,
                         const vector<vector<uint32_t>>& polaczenia, const vector<int8_t>& stan)
{
    uint32_t indeks0 = zakonczenia.front(), indeks=indeks0;
    int8_t c, cPrev=-1;
    vector<bool> odwiedzone(stan.size(), false);
    uint32_t licznik=0; // zlicza przedzialy
    for (uint32_t ii=0; ii<stan.size(); ii++)
    {
        c = stan[indeks];
        if (c!=cPrev)
        {
            licznik++;
            cPrev=c;
        }
        odwiedzone[indeks]=true;
        if (odwiedzone[polaczenia[indeks][0]]==false)
            indeks = polaczenia[indeks][0];
        else
            indeks = polaczenia[indeks][1];
    }
    return licznik;
}

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

    uint32_t ileTestow, n;
    cin>>ileTestow;

    for(uint32_t test=0; test<ileTestow; test++)
    {
        cin>>n;
        vector<int8_t> stanPocz(n), stanKon(n);
        vector<vector<uint32_t>> polaczenia(n);
        wczytajDane(stanPocz, stanKon, polaczenia);

        if (czyIdentyczne(stanPocz, stanKon))
            cout<<"TAK"<<endl;
        else if(czyDwaKolory(stanPocz)==false && !(czyDwaKolory(stanKon)==false && stanPocz[0]==stanKon[0]))
            cout<<"NIE"<<endl;
        else
        {
            vector<uint32_t> rozwidlenia; // wierzcholki z ktorych wychodza 3+ krawedzie
            vector<uint32_t> zakonczenia; // wierzcholki z ktorych wychodzi tylko 1 krawedz
            for (uint32_t ii=0; ii<polaczenia.size(); ii++)
                if(polaczenia[ii].size()==1)
                    zakonczenia.push_back(ii);
                else if(polaczenia[ii].size()>=3)
                    rozwidlenia.push_back(ii);

            if (rozwidlenia.empty()) // graf liniowy
                // rozw istnieje jesli liczba przedzialow (spojnych odcinkow w jednym kolorze) w koncowym grafie jest mniejsza
                // niz w poczatkowym albo gdy jest rowna i zaczynaja sie tym samym kolorem
            {
                uint32_t przedzialyPocz = zliczPrzedzialy(zakonczenia, polaczenia, stanPocz);
                uint32_t przedzialyKon  = zliczPrzedzialy(zakonczenia, polaczenia, stanKon);
                if(przedzialyKon < przedzialyPocz)
                    cout<<"TAK"<<endl;
                else if (przedzialyKon == przedzialyPocz && stanPocz[zakonczenia.front()]==stanKon[zakonczenia.front()])
                    cout<<"TAK"<<endl;
                else
                    cout<<"NIE"<<endl;
            }
            else // graf rozgaleziony
                // rozwiazanie istnieje jezeli w stanie koncowym istnieja 2 sasiadujace wierzcholki tego samego koloru
            {
                bool znalezione = false;
                for(uint32_t index=0; index<n; index++)
                {
                    int8_t val = stanKon[index];
                    for (auto it = polaczenia[index].begin(); it!= polaczenia[index].end(); ++it)
                        if (stanKon[*it]==val)
                        {
                            znalezione=true;
                            break;
                        }
                    if (znalezione)
                        break;
                }
                if (znalezione)
                    cout<<"TAK"<<endl;
                else
                    cout<<"NIE"<<endl;
            }
        }

    }

    return 0;
}