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

class dsu {
  public:
    vector<int> parents;
    vector<int> sizes;
    dsu (int n) {
      parents.resize(n);
      iota(parents.begin(), parents.end(), 0);
      sizes.resize(n, 1);
    }
    int root(int u) {
      return parents[u] == u ? u : parents[u] = root(parents[u]);
    }
    bool join(int u, int v) {
      int a = root(u);
      int b = root(v);
      if (a == b) return 0;
      if (sizes[a] > sizes[b]) swap(a, b);
      parents[a] = b;
      sizes[b] += sizes[a];
      return 1;
    }
};

int main () {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int T;
  cin >> T;
  while (T--) {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> G(n);
    vector<int> a(n), cnt(k);
    vector<vector<int>> verts(k);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      a[i]--;
      cnt[a[i]]++;
      verts[a[i]].emplace_back(i);
    }
    for (int i = 0; i < m; i++) {
      int u, v;
      cin >> u >> v;
      u--, v--;
      G[u].push_back(v);
      G[v].push_back(u);
    }

    vector<int> component_queue;
    dsu D1(n), D2(n);
    vector<int> inactive(n);
    auto join1 = [&] (int u, int v) {
      u = D1.root(u);
      v = D1.root(v);
      if (u == v) return;
      assert(a[u] == a[v]);
      D1.join(u, v);
      if (--cnt[a[u]] == 1) component_queue.emplace_back(a[u]);
    };

    vector<map<int, int>> reprs(n);
    for (int i = 0; i < n; i++) {
      reprs[i][a[i]] = i;
    }

    auto join2 = [&] (int u, int v) {
      u = D2.root(u);
      v = D2.root(v);
      if (u == v) return;
      D2.parents[u] = v;
      if (reprs[v].size() < reprs[u].size()) swap(reprs[u], reprs[v]);
      for (auto& [c, x]: reprs[u]) {
        if (reprs[v].count(c)) join1(reprs[v][c], x);
        else reprs[v][c] = x;
      }
    };

    auto deactivate = [&] (int v) {
      inactive[v] = 1;
      for (auto u: G[v]) {
        if (!inactive[u]) {
          if (reprs[v].count(a[u])) {
            join1(reprs[v][a[u]], u);
          }
          else reprs[v][a[u]] = u;
        }
      }
      for (auto u: G[v]) {
        if (inactive[u]) join2(v, u);
      }
    };

    for (int i = 0; i < k; i++) {
      if (cnt[i] <= 1) component_queue.emplace_back(i);
    }
    for (int v = 0; v < n; v++) {
      for (int u: G[v]) {
        if (a[u] == a[v]) join1(u, v);
      }
    }

    for (int i = 0; i < (int)component_queue.size(); i++) {
      int c = component_queue[i];
      for (int v: verts[c]) deactivate(v);
    }
    cout << ((int)component_queue.size() == k ? "TAK" : "NIE") << '\n';
  }
}