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

using namespace std;

#define MAXN 100003

int t, n;

int colors[2][MAXN];

int main() {

   cin >> t;

   while(t--) {

      cin >> n;

      int seen[2][2] = { {0, 0}, {0, 0} };
      
      for(int j = 0; j < 2; j++) {
         for(int i = 0; i < n; i++) {
            char c;
            cin >> c;
            if(c == '0') {
               colors[j][i] = 0;
               seen[j][0] = 1;
            } else if(c == '1') {
               colors[j][i] = 1;
               seen[j][1] = 1;
            } else {
               return 1;
            }
         }
      }


      vector<int> tree[n];
      bool visited[n];
      for(int i = 0; i < n; i++) {
         visited[i] = false;
      }

      for(int i = 0; i < n - 1; i++) {
         int a, b;
         cin >> a >> b;
         a--;
         b--;
         tree[a].push_back(b);
         tree[b].push_back(a);
      }

      if((seen[1][0] > seen[0][0]) || (seen[1][1] > seen[0][1])) {
         cout << "NIE" << endl;
         continue;
      }

      bool ok = true;
      for(int i = 0; i < n; i++) {
         if(colors[0][i] != colors[1][i]) {
            ok = false;
            break;
         }
      }
      if(ok) {
         cout << "TAK" << endl;
         continue;
      }

      int leaf = -1;
      int maxdeg = -1;

      for(int i = 0; i < n; i++) {
         int v = tree[i].size();
         if(v == 1) {
            leaf = i;
         }
         maxdeg = max(maxdeg, v);
      }

      if(maxdeg > 2) {
         bool ok = true;
         queue< pair<int, int> > q;
         q.push(make_pair(leaf, colors[1][leaf]));
         visited[leaf] = true;
         while(!q.empty()) {
            pair<int, int> v = q.front();
            q.pop();
            int i = v.first;
            // cout << "visiting " << i << endl;
            int c = v.second;
            if(colors[1][i] != c) {
               ok = false;
               break;
            }
            for(int w = 0; w < tree[i].size(); w++) {
               if(!visited[tree[i][w]]) {
                  visited[tree[i][w]] = true;
                  q.push(make_pair(tree[i][w], 1 - c));
               }
            }
         }
         cout << (ok ? "NIE" : "TAK") << endl;
      } else {
         //cout << "line" << endl;
         int s1 = 0, s2 = 0;
         int c1 = colors[0][leaf], c2 = colors[1][leaf];
         queue<int> q;
         q.push(leaf);
         visited[leaf] = true;
         while(!q.empty()) {
            int v = q.front();
            //cout << v << endl;
            q.pop();
            if(c1 != colors[0][v]) {
               c1 = 1 - c1;
               s1++;
            }
            if(c2 != colors[1][v]) {
               c2 = 1 - c2;
               s2++;
            }
            for(int w = 0; w < tree[v].size(); w++) {
               if(!visited[tree[v][w]]) {
                  visited[tree[v][w]] = true;
                  q.push(tree[v][w]);
               }
            }
         }
         if(s1 > s2 || (s1 == s2 && c1 == c2 && colors[0][leaf] == colors[1][leaf])) {
            cout << "TAK" << endl;
         } else {
            cout << "NIE" << endl;
         }

      }

   }

}