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
144
145
146
147
148
149
150
151
152
153
154
155
#include <bits/stdc++.h>
#define rep(i, p, k) for (int i = (p); i < (k); ++i)
#define all(v) (v).begin(), (v).end()
#define ll long long
#define fi first
#define sc second
#ifndef DEBUG
#define debug(...)
#else
#include "debug.h"
#endif
using namespace std;

struct DSU {
  vector<int> p;
  DSU(int n) : p(n, -1) {}
  int find(int x) { return p[x] < 0 ? x : p[x] = find(p[x]); }
  int unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y)
      return -1;
    if (p[x] > p[y])
      swap(x, y);
    p[x] += p[y];
    p[y] = x;
    return x;
  }
  int size(int x) { return -p[find(x)]; }
  bool is_rep(int x) { return p[x] < 0; }
};

struct bComponent {
  // colour -> index of vertex from connected live component
  unordered_map<int, int> live_nei;
  int is_on = false;
};

bool solve() {
  int n, m, k;
  cin >> n >> m >> k;
  vector<int> cols(n);
  vector<vector<int>> cc(k);
  rep(i, 0, n) {
    int x;
    cin >> x;
    cols[i] = --x;
    cc[x].push_back(i);
  }
  vector<vector<int>> g(n);
  vector<int> is_black(n);
  vector<int> is_queued(k);
  rep(i, 0, m) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  DSU black_dsu(n);
  DSU live_dsu(n);

  vector<bComponent> b_comps(n);
  queue<int> proccess_queue;

  auto queue_if_ready = [&](int v) {
    int c = cols[v];
    if (is_queued[c])
      return;
    if (live_dsu.size(v) != (int)cc[cols[v]].size())
      return;
    proccess_queue.push(c);
    is_queued[c] = true;
  };

  auto merge_live = [&](int v, int u) {
    v = live_dsu.find(v);
    u = live_dsu.find(u);
    int x = live_dsu.unite(v, u);
    if (x == -1)
      return;
    queue_if_ready(x);
  };

  auto merge_black = [&](int v, int u) {
    v = black_dsu.find(v);
    u = black_dsu.find(u);
    if (u == v)
      return u;
    int p = black_dsu.unite(v, u);
    if (p == v)
      swap(u, v);
    auto &P = b_comps[p];
    auto &V = b_comps[v];
    if (P.live_nei.size() < V.live_nei.size())
      P.live_nei.swap(V.live_nei);
    for (auto [c, vv] : V.live_nei) {
      if (auto it = P.live_nei.find(c); it != P.live_nei.end()) {
        merge_live(it->sc, vv);
      } else {
        P.live_nei[c] = vv;
      }
    }
    b_comps[v].is_on = false;
    return p;
  };

  auto process_vertex = [&](int v) {
    auto &bc = b_comps[v];
    bc.is_on = true;
    const int col = cols[v];
    // Construct b_comp for v
    for (auto u : g[v])
      if (!is_black[u] && cols[u] != col) {
        if (auto it = bc.live_nei.find(cols[u]); it != bc.live_nei.end()) {
          merge_live(it->sc, u);
        } else {
          bc.live_nei[cols[u]] = u;
        }
      }
    for (auto u : g[v])
      if (is_black[u])
        merge_black(v, u);
    is_black[v] = true;
  };

  auto process_colour = [&](int c) {
    for (auto v : cc[c])
      process_vertex(v);
  };

  rep(v, 0, n) queue_if_ready(v);

  rep(v, 0, n) for (auto u : g[v]) if (v < u && cols[v] == cols[u])
      merge_live(v, u);

  while (!proccess_queue.empty()) {
    auto c = proccess_queue.front();
    proccess_queue.pop();
    process_colour(c);
  }

  rep(v, 0, n) if (!is_black[v]) return false;
  return true;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--)
    cout << (solve() ? "TAK\n" : "NIE\n");
  return 0;
}