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
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
namespace IAOI_lib{
  class dsu{
    private:
      vector<int> a,s;
    public:
      dsu(int n):a(n),s(n,1){
        iota(a.begin(),a.end(),0);
      }
      int leader(int x){
        return a[x]==x?x:a[x]=leader(a[x]);
      }
      int size(int x){
        return s[leader(x)];
      }
      void merge(int x,int y){
        x=leader(x),y=leader(y);
        if(x==y)return;
        if(s[x]>s[y])swap(x,y);
        s[y]+=s[x],a[x]=y;
      }
      bool same(int x,int y){
        return leader(x)==leader(y);
      }
      vector<vector<int> > groups(){
        vector<int> id(a.size(),-1);
        int c=0;
        for(int i=0;i<a.size();i++)
          if(i==leader(i))id[i]=c++;
        vector<vector<int> > v(c);
        for(int i=0;i<a.size();i++)
          v[id[leader(i)]].emplace_back(i);
        return v;
      }
  };
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t; cin>>t;
  while(t--){
    int n,m,k; cin>>n>>m>>k;
    vector<int> a(n);
    for(auto &i:a)cin>>i,i--;
    vector<vector<int> > vt(k);
    for(int i=0;i<n;i++)
      vt[a[i]].emplace_back(i);
    vector<vector<int> > g(n);
    for(int i=0;i<m;i++){
      int u,v; cin>>u>>v;
      g[--u].emplace_back(--v);
      g[v].emplace_back(u);
    }
    vector<int> e(k);
    queue<int> q;
    for(int i=0;i<k;i++)
      if(e[i]+1>=vt[i].size())
        q.emplace(i);
    IAOI_lib::dsu d(n);
    auto mg=[&](int x,int y){
      if(d.same(x,y))return;
      d.merge(x,y);
      if(++e[a[x]]+1>=vt[a[x]].size())
        q.emplace(a[x]);
    };
    vector<int> f(n);
    iota(f.begin(),f.end(),0);
    vector<gp_hash_table<int,int> > s(n);
    auto leader=[&](auto &&self,int x)->int{
      return x==f[x]?x:f[x]=self(self,f[x]);
    };
    auto mg2=[&](int x,int y){
      x=leader(leader,x),y=leader(leader,y);
      if(x==y)return;
      if(s[x].size()>s[y].size())swap(x,y);
      for(auto [c,l]:s[x]){
        if(s[y].find(c)!=s[y].end())mg(l,s[y][c]);
        else s[y][c]=l;
      }
      f[x]=y,gp_hash_table<int,int>().swap(s[x]);
    };
    for(int u=0;u<n;u++)
      for(int v:g[u])
        if(u<v&&a[u]==a[v])mg(u,v);
    int dl=0;
    while(!q.empty()){
      int c=q.front(); dl++,q.pop();
      for(int u:vt[c]){
        a[u]=-1;
        sort(g[u].begin(),g[u].end(),[&](int x,int y){
          return a[x]<a[y];
        });
        for(int i=0;i<g[u].size();i++)
          if(~a[g[u][i]]){
            if(i&&a[g[u][i-1]]==a[g[u][i]])
              mg(g[u][i-1],g[u][i]);
            else s[u][a[g[u][i]]]=g[u][i];
          }
      }
      for(int u:vt[c])
        for(int v:g[u])
          if(a[v]<0)mg2(u,v);
    }
    cout<<(dl==k?"TAK\n":"NIE\n");
  }
  return 0;
}