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

string res_sign[2];

void calc_sign(int parent, int head, const string &input,
               const vector<vector<int>> &nei, bool num) {
  for (int i = 0; i < nei[head].size(); i++) {
    int neighbour = nei[head][i];
    // cerr << "parent: " << parent << endl;
    // cerr << "head: " << head << endl;
    // cerr << "neighbour: " << neighbour << endl;
    if (neighbour != parent) {
      if (input[neighbour] != input[head]) {  
        res_sign[num] += input[neighbour];
      }
      calc_sign(head, neighbour, input, nei, num);
    }
  }
}

signed main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    string s_beg, s_end;
    res_sign[0].clear();
    res_sign[1].clear();
    cin >> n >> s_beg >> s_end;
    // cerr << "n: " << n << endl;
    vector<vector<int>> nei(n);
    for (int i = 0; i < n - 1; i++) {
      int x, y;
      cin >> x >> y;
      nei[x - 1].push_back(y - 1);
      nei[y - 1].push_back(x - 1);
    }
    int cnt_1_beg = 0;
    int cnt_1_end = 0;
    for (int i = 0; i < n; i++) {
      if (s_beg[i] == '1') {
        cnt_1_beg++;
      }
      if (s_end[i] == '1') {
        cnt_1_end++;
      }
    }
    if (cnt_1_beg == n && cnt_1_end == n) {
      cout << "TAK" << endl;
    } else if (cnt_1_beg == 0 && cnt_1_end == 0) {
      cout << "TAK" << endl;
    } else if (cnt_1_beg == n && cnt_1_end < n) {
      cout << "NIE" << endl;
    } else if (cnt_1_beg == 0 && cnt_1_end > 0) {
      cout << "NIE" << endl;
    } else {
      bool has_3 = false;
      int head = -1;
      for (int i = 0; i < nei.size(); i++) {
        if (nei[i].size() > 2) {
          has_3 = true;
        }
        if (nei[i].size() == 1) {
          head = i;
        }
      }
      if (has_3) {
        cout << "TAK" << endl;
      } else {
        res_sign[0] += s_beg[head];
        res_sign[1] += s_end[head];
        calc_sign(head, head, s_beg, nei, 0);
        calc_sign(head, head, s_end, nei, 1);
        if (res_sign[0].size() > res_sign[1].size()) {
          cout << "TAK" << endl;
        } else if (res_sign[0].size() < res_sign[1].size()) {
          cout << "NIE" << endl;
        } else {
          if (res_sign[0] == res_sign[1]) {
            cout << "TAK" << endl;
          } else {
            cout << "NIE" << endl;
          }
        }
      }
    }
  }
}