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
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <set>

using namespace std;

vector<bool> koloryPocz, koloryKon;
vector<vector<int>> sasiedzi;
int n;
bool wszystkieRowne, takieSame;

void wczytaj() {
    ios_base::sync_with_stdio(false);
    string strPocz, strKon;
    int i, a, b;
    wszystkieRowne = true;
    takieSame = true;

    cin >> n >> strPocz >> strKon;

    koloryPocz.resize(n);
    koloryKon.resize(n);
    sasiedzi.clear();
    sasiedzi.resize(n);

    for (i = 0; i < n; i++) {
        koloryPocz[i] = strPocz[i] == '1';
        koloryKon[i] = strKon[i] == '1';

        wszystkieRowne = wszystkieRowne && (koloryPocz[i] == koloryPocz[0]);
        takieSame = takieSame && (koloryPocz[i] == koloryKon[i]);
    }

    for (i = 1; i < n; i++) {
        cin >> a >> b;
        a--; b--;
        sasiedzi[a].push_back(b);
        sasiedzi[b].push_back(a);
    }
}

int policzZmiany(int pocz, int kon, vector<bool>& kolory) {
    int poprz = pocz;
    int nast = sasiedzi[poprz][0];
    int zmiany = kolory[poprz] != kolory[nast] ? 1 : 0;
    vector<bool> odwiedzone(n, false);
    odwiedzone[poprz] = odwiedzone[nast] = true;

    while (nast != kon) {
        // cerr << poprz << ' ' << nast;
        // cerr << " " << sasiedzi[nast][0] << " " << sasiedzi[nast][1];
        // cerr << " " << odwiedzone[sasiedzi[nast][0]] << " " << odwiedzone[sasiedzi[nast][1]];
        // cerr << endl;
        int curr = nast;
        nast = sasiedzi[curr][0];
        if (odwiedzone[nast]) nast = sasiedzi[curr][1];        
        poprz = curr;
        odwiedzone[nast] = true;

        zmiany += kolory[poprz] != kolory[nast] ? 1 : 0;
    };

    // cerr << "------------" << endl;

    return zmiany;
}

bool rozwiaz() {
    vector<int> konce;

    for (int i = 0; i < n; i++) {
        if (sasiedzi[i].size() == 1) {
            konce.push_back(i);
            if (konce.size() == 3) {
                return true;
            }
        }
    }

    int zmianyPocz = policzZmiany(konce[0], konce[1], koloryPocz);
    int zmianyKon = policzZmiany(konce[0], konce[1], koloryKon);

    if (zmianyKon < zmianyPocz) {
        return true;
    } else if (zmianyKon > zmianyPocz) {
        return false;
    } else {
        return koloryPocz[konce[0]] == koloryKon[konce[0]];
    }
}


int main() {
    int t;

    cin >> t;
    while (t--) {
        wczytaj();
        bool daSie;

        if (takieSame) {
            daSie = true;
        } else if (wszystkieRowne) {
            daSie = false;
        } else {
            daSie = rozwiaz();
        }

        cout << (daSie ? "TAK" : "NIE") << endl;
    }

    return 0;
}