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
#include <bits/stdc++.h>
using namespace std;
const int MX=100100;
int t,n,m,k,num,fi,fr,x,y,c[MX],cnt[MX],pr[MX],rk[MX],p[MX],q[MX];
vector<int> g[MX],w[MX];
map<int,int> mp[MX];
int fs(int x) {
  if (pr[x]!=x) pr[x]=fs(pr[x]);
  return pr[x];
}
void unv(int x, int y) {
  if (x==y) return;
  if (c[x]==0 && c[y]==0) {
    if (mp[x].size()<=mp[y].size()) swap(x,y);
    p[y]=x;
  }
  for (auto it=mp[y].begin(); it!=mp[y].end(); it++) {
    auto xt=mp[x].find(it->first);
    if (xt!=mp[x].end()) {
      if (it->second!=xt->second) {
        int ii=fs(it->second);
        int xx=fs(xt->second);
        if (ii==xx) continue;
        if (--cnt[it->first]==1) q[fr++]=it->first;
        if (rk[xx]>=rk[ii]) {
          xt->second=pr[ii]=xx;
          if (rk[xx]==rk[ii]) ++rk[xx];
        } else xt->second=pr[xx]=ii;
      }
    } else mp[x][it->first]=it->second;
  }
}
int fsv(int x) {
  if (p[x]!=x) p[x]=fsv(p[x]);
  return p[x];
}
int main() {
  scanf("%d",&t);
  while (t--) {
    num=fi=fr=0;
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1; i<=k; i++) {
      cnt[i]=0;
      w[i].clear();
    }
    for (int i=1; i<=n; i++) {
      scanf("%d",&c[i]);
      w[c[i]].push_back(i);
      ++cnt[c[i]];
      p[i]=i;
      g[i].clear();
      mp[i].clear();
      mp[i][c[i]]=++num;
      pr[num]=num;
      rk[num]=0;
    }
    for (int i=1; i<=k; i++) if (cnt[i]<=1) q[fr++]=i;
    while (m--) {
      scanf("%d%d",&x,&y);
      g[x].push_back(y);
      g[y].push_back(x);
      if (c[x]==c[y]) unv(fsv(x),fsv(y));
    }
    while (fi<fr) {
      int i=q[fi++];
      for (int v: w[i]) c[v]=0;
      for (int v: w[i]) for (int j: g[v]) unv(fsv(v),fsv(j));
    }
    puts((fr==k)?"TAK":"NIE");
  }
  return 0;
}