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

using namespace std;

const int MAXN = 100010;

vector<int> G[MAXN];


bool test(int n, const string &s0, const string &s1) {
  if (s0 == s1) return true;


  int s00 = 0; int s01 = 0;
  for (int i = 0; i < n; i++) {
    if (s0[i] == '0') s00++; else s01++;
  }
  if (s00 == 0 || s01 == 0) return false;


  bool bicolored = true;
  int maxd = 0;
  int leaf = 0;
  for (int i = 1; i <= n; i++) {
    maxd = max(maxd, (int)G[i].size());
    if (G[i].size() == 1) leaf = i;
    for (int j : G[i]) {
      if (s1[i - 1] == s1[j - 1]) bicolored = false;
    }
  }
  if (bicolored) return false;


  if (maxd > 2) return true;

  char c0 = s0[leaf - 1];
  char c1 = s1[leaf - 1];
  int pv = -1;
  int segs0 = 1;
  int segs1 = 1;
  for (int i = 1; i < n; i++) {
    int prev2 = leaf;
    leaf = G[leaf][0] == pv ? G[leaf][1] : G[leaf][0];
    pv = prev2;
    if (s0[leaf - 1] != s0[pv - 1]) segs0++;
    if (s1[leaf - 1] != s1[pv - 1]) segs1++;
  }

  if (segs0 < segs1) return false;
  if (segs0 == segs1 && c0 != c1) return false;
  return true;
}


int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    string s0, s1;

    cin >> n;
    cin >> s0 >> s1;
    for (int i = 0; i < n - 1; i++) {
      int x, y;
      cin >> x >> y;
      G[x].push_back(y);
      G[y].push_back(x);
    }

    puts(test(n, s0, s1) ? "TAK" : "NIE");

    for (int i = 1; i <= n; i++) {
      G[i].clear();
    }
  }
}