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
#include <bits/stdc++.h>
using namespace std;

#define ll long long
vector<int> colors;
vector<int> new_colors;
vector<int> count_adj;
vector<vector<int>> adjacents;
vector<bool> can_be_red;
vector<bool> can_be_black;

void DFS(int node, int parent) {
  for (auto const &adj : adjacents[node]) {
    if (adj != parent) {
      DFS(adj, node);
    }
  }
  for (auto const &adj : adjacents[node]) {
    if (can_be_red[adj] || colors[adj] + colors[node] < 2) {
      can_be_red[node] = true;
    }
    if (can_be_black[adj] || colors[adj] + colors[node]) {
      can_be_black[node] = true;
    }
  }
}

void Solve() {
  int vertices;
  cin >> vertices;
  colors.resize(vertices + 1);
  count_adj = vector<int>(vertices + 1, 0);
  new_colors.resize(vertices + 1);
  colors[0] = -1;
  new_colors[0] = -1;
  adjacents.clear();
  adjacents.resize(vertices + 1);
  string col1, col2;
  cin >> col1 >> col2;
  for (int i = 0; i < col1.size(); i++) {
    colors[i + 1] = col1[i] - '0';
  }
  for (int i = 0; i < col2.size(); i++) {
    new_colors[i + 1] = col2[i] - '0';
  }
  for (int i = 1; i < vertices; i++) {
    int a, b;
    cin >> a >> b;
    adjacents[a].push_back(b);
    adjacents[b].push_back(a);
    count_adj[a]++;
    count_adj[b]++;
  }

  vector<bool> vis(vertices + 1);
  can_be_red = vector<bool>(vertices + 1);
  can_be_black = vector<bool>(vertices + 1);

  for (int i = 1; i <= vertices; i++) {
    if (count_adj[i] != 1) {
      DFS(i, 0);
      break;
    }
  }

  for (int i = 1; i <= vertices; i++) {
    if (new_colors[i] == 1 && !can_be_black[i] && colors[i] != 1) {
      cout << "NIE\n";
      return;
    }
    if (new_colors[i] == 0 && !can_be_red[i] && colors[i] != 0) {
      cout << "NIE\n";
      return;
    }
  }
  cout << "TAK\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  ll tests;
  cin >> tests;
  while (tests--) {
    Solve();
  }
}