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
#include <cstdio>
#include <vector>

using namespace std;

typedef vector<vector<int>> E;
bool isPath(E& e) {
  int cnt = 0;
  for (int i=0; i<e.size(); ++i) {
    if (e[i].size() < 2) ++cnt;
  }
  return cnt < 3;
}

int numFlips(E& e, vector<char>& a, int p = 0, int r = 0) {
  int cnt = 0;
  for (int q : e[p]) {
    if (q == r) continue;
    cnt += numFlips(e, a, q, p);
    if (a[q] != a[p]) ++cnt;
  }
  return cnt;
}

void tak() {
  printf("TAK\n");
}

void nie() {
  printf("NIE\n");
}

void solve() {
  int n; scanf("%d", &n);
  vector<char> a(n), b(n);
  for (int i=0; i<n; ++i) scanf(" %c", &a[i]);
  for (int i=0; i<n; ++i) scanf(" %c", &b[i]);

  E e(n);
  for (int i=0; i<n-1; ++i) {
    int x, y; scanf("%d %d", &x, &y); --x; --y;
    e[x].push_back(y);
    e[y].push_back(x);
  }

  int flipsA = numFlips(e, a);
  int flipsB = numFlips(e, b);
  if (isPath(e)) {
    if (flipsA < flipsB) { nie(); return; }
    if (flipsA > flipsB) { tak(); return; }
    for (int i=0; i<n; ++i) {
      if (e[i].size() < 2) {
        if (a[i] == b[i]) tak(); else nie();
        return;
      }
    }
  }
 
  bool same = true;
  for (int i=0; i<n; ++i) if (a[i] != b[i]) same = false;
  if (same) { tak(); return; }

  if (flipsA < 1) { nie(); return; }
  if (flipsB < n-1) tak(); else nie();
}

int main() {
  int t; scanf("%d", &t);
  for (int s=0; s<t; ++s) solve();
  return 0;
}