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

#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

#ifdef LOCAL
auto operator<<(auto& o, auto x) -> decltype(x.first, o);
auto operator<<(auto& o, auto x) -> decltype(x.end(), o) {
  o << "{";
  for (int i = 0; auto y : x) o << ", " + !i++ * 2 << y;
  return o << "}"; }
auto operator<<(auto& o, auto x) -> decltype(x.first, o) {
  return o << "(" << x.first << ", " << x.second << ")"; }
void __print(auto... x) { ((cerr << x << " "), ...) << endl; }
#define debug(x...) __print("[" #x "]:", x)
#else
#define debug(...) 2137
#endif

const int N = 100100;
int n, m, k;
vi g[N];
int a[N];
vi ludzie[N];
map<int, int> sas[N];
queue<int> q;
int p1[N], p2[N];

int find1(int x) { return p1[x] < 0 ? x : p1[x] = find1(p1[x]); }
int find2(int x) { return p2[x] < 0 ? x : p2[x] = find2(p2[x]); }
void lacz1(int x, int y) {
  x = find1(x);
  y = find1(y);
  if (x == y) return;
  if (-p1[x] < -p1[y]) swap(x, y);
  p1[x] += p1[y];
  p1[y] = x;
  if (-p1[x] == sz(ludzie[a[x]])) q.push(a[x]);
}

void solve() {
  cin >> n >> m >> k;
  rep(i, 0, n) g[i].clear(), sas[i].clear();
  rep(i, 0, k) ludzie[i].clear();
  rep(i, 0, n) {
    cin >> a[i];
    a[i]--;
    ludzie[a[i]].push_back(i);
  }
  rep(i, 0, m) {
    int u, v;
    cin >> u >> v;
    u--; v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  q = queue<int>();
  rep(i, 0, n) {
    p1[i] = p2[i] = -1;
    if (sz(ludzie[a[i]]) == 1) q.push(a[i]);
  }
  rep(i, 0, n) for (int j : g[i]) if (a[i] == a[j]) lacz1(i, j);
  int suma = 0;
  while (sz(q)) {
    int kolor = q.front(); q.pop();
    for (int u : ludzie[kolor]) a[u] = -1;
    suma += sz(ludzie[kolor]);
    for (int u : ludzie[kolor]) {
      for (int v : g[u]) if (a[v] != -1) {
        if (sas[u].count(a[v])) lacz1(v, sas[u][a[v]]);
        sas[u][a[v]] = find1(v);
      }
    }
    for (int u : ludzie[kolor]) {
      for (int v : g[u]) if (a[u] == -1 && a[v] == -1) {
        int x = find2(u);
        int y = find2(v);
        if (x == y) continue;
        if (-p2[x] < -p2[y]) swap(x, y);
        p2[x] += p2[y];
        p2[y] = x;
        for (auto [kol, repr] : sas[y]) {
          if (sas[x].count(kol)) lacz1(sas[x][kol], repr);
          sas[x][kol] = find1(repr);
        }
        map<int, int> puste;
        swap(puste, sas[y]);
      }
    }
  }
  cout << (suma == n ? "TAK" : "NIE") << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) solve();
}