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
// 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i, p, k) for(int i(p); i < (k); ++i)
typedef long long int ll;
typedef long double ld;
template <typename T = int> inline T in()
{
    T x;
    std::cin >> x;
    return x;
}
constexpr int maxn = 1e5 + 3;
std::vector <int> tre[maxn];
void kra(int a, int b){tre[a].push_back(b); tre[b].push_back(a); }
bool bod(int n)
{
    std::string s('#' + in<std::string>()), t('#' + in<std::string>());
    rep(i, 1, n+1)tre[i].clear();
    rep(i, 1, n) kra(in(), in());
    if(s == t)return 1;
    bool j[2]{0, 0};
    rep(i, 1, s.size())j[s[i] - '0'] = 1;
    if(!(j[0] && j[1]))return 0;
    int wt(0), ws(0);
    rep(i, 1, n+1)for(auto j: tre[i])wt += t[i] == t[j];
    if(!wt)return 0;
    rep(i, 1, n+1)if(tre[i].size() > 2)return 1;
    rep(i, 1, n+1)for(auto j: tre[i])ws += s[i] == s[j];
    bool rl(0);
    rep(i, 1, n+1)if(tre[i].size() == 1)rl |= s[i] != t[i];
    if(ws == wt && !rl)return 1;
    if(wt > ws)return 1;
    return 0;
}
int main()
{
    std::cin.tie(nullptr); std::cout.tie(nullptr); std::ios_base::sync_with_stdio(0);
    int t(in());
    while (t--)std::cout << (bod(in()) ? "TAK" : "NIE")<<'\n' ;
    return 0;
}