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
#include "bits/stdc++.h" // Ignacy Boehlke
using namespace std;     // XIII LO Szczecin
template<class A, class B> ostream& operator << (ostream& os, const pair<A, B>& p) {return os << '{' << p.first << ", " << p.second << '}';}
template<class T> auto operator << (ostream& os, const T& v) -> decltype(v.begin(), os) {os << '{';for (auto i : v) os << i << ", ";return os << '}';}
#ifdef DEBUG
#define D(x...) x
#else
#define D(x...)
#endif
#define LN(x) D(cerr << #x << ": " << x << ' ')
#define LOG(x) D(cerr << #x << ": " << x << '\n')
#define ssize(x) ((int)x.size())
#define FOR(a, b, c) for(int a = (b); a <= (c); ++a)
#define REP(a, b) FOR(a, 0, b - 1)
#define ALL(x) (x).begin(), (x).end()
#define fi first
#define se second
using ll = long long;

void solve() {
    int n;
    scanf("%d ", &n);
    vector<bool> in(n), out(n);
    REP(i, n) in[i] = getchar() - '0';
    getchar();
    REP(i, n) out[i] = getchar() - '0';

    vector<int> ng(n);
    int c1 = 0, c2 = 0;
    bool line = true;
    REP(i, n - 1) {
        int a, b;
        scanf("%d%d", &a, &b); --a; --b;
        c1 += in[a] != in[b];
        c2 += out[a] != out[b];
        line = line && (++ng[a] < 3) && (++ng[b] < 3);
    }
    bool e[2] = {false, false};
    int k = 0;
    if (line) REP(i, n) if (ng[i] == 1) e[k++] = (in[i] == out[i]);

    if (n == 1) puts(in == out ? "TAK" : "NIE");
    else puts((c2 == n - 1 && in != out) || (!c1 && (c2 || (!c2 && in[0] != out[0]))) || (line && (c1 - !e[0] - !e[1] < c2)) ? "NIE" : "TAK");
}

int main() {
    int T;
    scanf("%d", &T);
    REP(i, T) solve();
}