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
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <iostream>
using namespace std;

int t;
int start[100007];
int finish[100007];
int edge[100007][2];
int deg[100007];

void print_ans(bool ans) {
  if (ans)
    cout << "TAK" << '\n';
  else
    cout << "NIE" << '\n';
  return;
}

int main()
{
  ios_base::sync_with_stdio(0);

  cin >> t;

  for (int test=0; test<t; test++) {
    int n;
    cin >> n;

    char c;

    bool start_has_red=false, start_has_black=false;

    // colors of start
    for (int i=0; i<n; i++) {
      cin >> c;
      if (c=='0') {
        start[i+1] = 0;
        start_has_red = true;
      }
      else {
        start[i+1] = 1;
        start_has_black = true;
      }
    }

    // colors of end
    for (int i=0; i<n; i++) {
      cin >> c;
      if (c=='0')
        finish[i+1] = 0;
      else
        finish[i+1] = 1;
    }

    for (int i=0; i<n-1; i++)
      cin >> edge[i][0] >> edge[i][1];

    if (not start_has_red) {
      // end has to be entire black
      bool ans=true;
      for (int i=1; i<n+1; i++)
        if (finish[i] == 0) {
          ans = false;
          break;
        }
      print_ans(ans);
      continue;
    }

    if (not start_has_black) {
      // end has to be entire red
      bool ans=true;
      for (int i=1; i<n+1; i++)
        if (finish[i] == 1) {
          ans = false;
          break;
        }
      print_ans(ans);
      continue;
    }

    bool end_has_mono_edge = false;
    bool end_has_branching = false;
    int end_multi_edges = 0;
    for (int i=0; i<n+1; i++)
      deg[i] = 0;

    for (int i=0; i<n-1; i++) {
      if (finish[edge[i][0]] == finish[edge[i][1]])
        end_has_mono_edge = true;
      else
        end_multi_edges++;
      deg[edge[i][0]]++;
      if (deg[edge[i][0]] > 2)
        end_has_branching = true;
      deg[edge[i][1]]++;
      if (deg[edge[i][1]] > 2)
        end_has_branching = true;
    }

    if (not end_has_mono_edge) {
      // end has to be equal to start
      bool ans = true;
      for (int i=1; i<n+1; i++)
        if (start[i] != finish[i]) {
          ans = false;
          break;
        }
      print_ans(ans);
      continue;
    }

    if (end_has_branching) {
      print_ans(true);
      continue;
    }

    int start_multi_edges = 0;
    for (int i=0; i<n-1; i++)
      if (start[edge[i][0]] != start[edge[i][1]])
        start_multi_edges++;

    if (end_multi_edges < start_multi_edges) {
      print_ans(true);
      continue;
    }

    if (end_multi_edges > start_multi_edges) {
      print_ans(false);
      continue;
    }

    int leaf;
    for (int i=1; i<n+1; i++)
      if (deg[i] == 1) {
        leaf = i;
        break;
      }

    print_ans(start[leaf]==finish[leaf]);
  }

  return 0;
}