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
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <unordered_set>

using namespace std;

int n;

struct link_t
{
    int a;
    int b;
};
vector<link_t> links;

typedef unsigned int long long ull;

ull initial_state=0;
ull target_state=0;
unordered_set<ull> s;

ull invert_bit(ull v,int index)
{
    ull mask=((ull)1<<index);
    ull res=(v&mask)?(v&(~mask)):(v|mask);
    return res;
}

bool visit(ull state)
{
    {
        auto it=s.find(state);
        if(it!=s.end())
            return false;
    }
	if (state == target_state)
		return true;
	s.insert(state);
    for(int i=0;i<n-1;++i)
    {
        const bool is_a_set=(state&((ull)1<<links[i].a))!=0;
        const bool is_b_set=(state&((ull)1<<links[i].b))!=0;
        if(is_a_set!=is_b_set)
        {
            if(visit(invert_bit(state,links[i].a)))
                return true;
            if(visit(invert_bit(state,links[i].b)))
                return true;
        }
    }
    return false;
}

bool solve()
{
    s.clear();
    return visit(initial_state);
}

int main()
{
#ifdef _DEBUG
    ifstream input("input0.txt");
#else
    #define input cin
#endif

	string s1,s2;

    int t;
    input>>t;
    for(int i=0;i<t;++i)
    {
        input>>n>>s1>>s2;
        initial_state=target_state=0;
        for(int j=0;j<n;++j)
        {
            if(s1[j]=='1')
                initial_state|=((ull)1<<j);
            if(s2[j]=='1')
                target_state|=((ull)1<<j);
        }
        links.resize(n-1);
        for(int j=0;j<n-1;++j)
        {
            int a,b;
            input>>a>>b;
            --a;
            --b;
            links[j]={a,b};
        }
        bool result=solve();
        cout<<(result?"TAK":"NIE")<<endl;
    }

    return 0;
}