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
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
int n, k;

vector<int> par, sz, val;
vector<set<int>> comps;
queue<int> Q;

int find(int a) {
   if (par[a] < 0) return a;
   return par[a] = find(par[a]);
}

bool merge(int a, int b) {
   int u = find(a);
   int v = find(b);
   if (u == v) return false;
   if (comps[u].size() < comps[v].size()) swap(u, v);
   for (int p : comps[v]) {
      auto [iter, added] = comps[u].insert(p);
      if (!added) {
         sz[p]--;
         if (sz[p] <= 1) Q.push(p);
      }
   }
   comps[v].clear();
   par[v] = u;

   // cerr << a << ' ' << b << "  " << u << ' ' << v << endl;
   // for (int i = 0; i < k; i++) {
   //    cerr << sz[i] << ' ';
   // }
   // cerr << endl;
   // for (int i = 0; i < n; i++) {
   //    cerr << "i:" << i << ' ';
   //    for (auto a : comps[i]) {
   //       cerr << ' ' << a;
   //    }
   //    cerr << endl;
   // }
   // cerr << endl;

   return true;
}

void test_case() {
   // int n;
   // int k;
   int m;
   cin >> n >> m >> k;

   val.assign(n, 0);
   par.assign(n, -1);
   comps.assign(n, set<int>());
   sz.assign(k, 0);
   vector<vector<int>> verts(k), adj(n);
   for (int i = 0; i < n; i++) {
      int a; cin >> a;
      a--; val[i] = a;
      verts[a].push_back(i);
      sz[a]++;
      comps[i].insert(a);
   }
   for (int i = 0; i < m; i++) {
      int a, b;
      cin >> a >> b;
      a--; b--;
      if (val[a] == val[b]) merge(a, b);
      adj[a].push_back(b);
      adj[b].push_back(a);
   }

   for (int i = 0; i < k; i++) {
      if (sz[i] == 1) Q.push(i);
   }

   while (!Q.empty()) {
      int v = Q.front(); Q.pop();
      // cerr << v << ' ';
      for (int a : verts[v]) {
         for (int b : adj[a]) {
            merge(a, b);
         }
      }
   }

   for (int i = 0; i < k; i++) {
      if (sz[i] > 1) {
         cout << "NIE" << endl;
         return;
      }
   }
   cout << "TAK" << endl;
   return;
}

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

   int q; cin >> q;
   while (q--) {
      test_case();
   }

   return 0;
}