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

using namespace std;

struct kraw
{
    int a, b;
};

int n;
vector<string> col(2);
bool odp;
set<string> odw;
vector<kraw> a;

void o(char& c)
{
    if (c == '0')
        c = '1';
    else
        c = '0';
}

void rec(string akt)
{
    if (akt == col[1])
    {
        odp = true;
        return;
    }
    for (int i = 0; i < a.size(); ++i)
    {
        if (akt[a[i].a] != akt[a[i].b])
        {
            o(akt[a[i].a]);
            if (odw.find(akt) == odw.end())
            {
                odw.insert(akt);
                rec(akt);
            }
            o(akt[a[i].a]);
            o(akt[a[i].b]);
            if (odw.find(akt) == odw.end())
            {
                odw.insert(akt);
                rec(akt);
            }
            o(akt[a[i].b]);
        }
    }
}

void Solve()
{
    cin >> n >> col[0] >> col[1];
    a.clear();
    for (int i = 0; i < n - 1; ++i)
    {
        int x, y;
        cin >> x >> y;
        a.push_back({x - 1, y - 1});
    }
    odw.clear();
    odp = false;
    rec(col[0]);
    if (odp)
        cout << "TAK" << endl;
    else
        cout << "NIE" << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i)
        Solve();
    return 0;
}