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
#ifndef UNCLE
 #pragma GCC optimize("O3,unroll-loops")
#endif

#include <bits/stdc++.h>
using namespace std;

#define FOR(i,p,q) for(int i=(p); i<=(q); ++i)
#define ROF(i,p,q) for(int i=(p); i>=(q); --i)
#define REP(i,q) for(int i=0; i<(q); ++i)
#define pb push_back
#define as assign
#define rz resize
#define Co const
#define al(X) X.begin(), X.end()
#define ral(X) X.rbegin(), X.rend()
#define sz(X) (int)((X).size())
#define ckmx(a,b) a=max(a,b)
#define ckmn(a,b) a=min(a,b)
#define V vector
typedef long long ll;
typedef long double ld;
typedef mt19937_64 mt;
#ifndef UNCLE
 typedef basic_string<bool> vb;
 typedef basic_string<int> vi;
 typedef basic_string<ll> vl;
#else
 typedef V<bool> vb;
 typedef V<int> vi;
 typedef V<ll> vl;
 #endif
 
 constexpr ll INFl=(ll)1e18+14;
 constexpr int INFi=1e9+14, MX_N=5e5+14;
 
 int N,M,K;
 
vi qt,tdo,cl;
struct FUC{
    vi ft;
    void Bu0(){
        ft.as(N,-1);
    }
    int Fi(int v){
        return (ft[v]<0?v:ft[v]=Fi(ft[v]));
    }
    bool Uni(int u,int v){
        u=Fi(u),v=Fi(v);
        if(u==v) return 0;
        if(-ft[u]<-ft[v]) swap(u,v);
        ft[u]+=ft[v],ft[v]=u;
        --qt[cl[u]];
        if(qt[cl[u]]==1) tdo.pb(cl[u]); //pozwalam na qt=0;
        return 1;
    }
};
FUC fuc;
struct FUB{
    vi ft;
    V<unordered_map<int,int>> mp;
    void Bu0(){
        ft.as(N,-1);
        mp.as(N,unordered_map<int,int>());
    }
    int Fi(int v){
        return (ft[v]<0?v:ft[v]=Fi(ft[v]));
    }
    bool Uni(int u,int v){
        u=Fi(u),v=Fi(v);
        if(u==v) return 0;
        if(-ft[u]<-ft[v]) swap(u,v);
        if(sz(mp[u])<sz(mp[v])) swap(mp[u],mp[v]);
        for(auto it=mp[v].begin();it!=mp[v].end();++it){
            if(mp[u].count(it->first)){
                fuc.Uni(mp[u][it->first],it->second);
            }
            else mp[u][it->first]=it->second;
        }
        mp[v].clear(); //nic nie daje ////////////////////////////////////////////////////////////////////////
        ft[u]+=ft[v],ft[v]=u;
        return 1;
    }
};

void Inpt(){
    cin>>N>>M>>K;
    cl.as(N,-1);
    tdo.clear();
    qt.as(K,0);
    V<vi> sn(N,vi()), ls(K,vi());
    REP(i,N) cin>>cl[i],--cl[i], ++qt[cl[i]],ls[cl[i]].pb(i);
    fuc.Bu0();
    FUB fub;
    fub.Bu0();
    int u,v;
    int aqt=K;
    REP(i,K){
        if(qt[i]==1) tdo.pb(i);
        else if(qt[i]==0) --aqt;
    }
    REP(_,M){
        cin>>u>>v,--u,--v, sn[u].pb(v),sn[v].pb(u);
        if(cl[u]==cl[v]) fuc.Uni(u,v);
    }
    while(!tdo.empty()){
        --aqt;
        int cc=tdo.back(); tdo.pop_back();
        qt[cc]=0;
        for(int &vv:ls[cc]){
            for(int &nv:sn[vv]){
                if(qt[cl[nv]]!=0){
                    if(fub.mp[fub.Fi(vv)].count(cl[nv])) fuc.Uni(fub.mp[fub.Fi(vv)][cl[nv]],nv);
                    else fub.mp[fub.Fi(vv)][cl[nv]]=nv;
                }else fub.Uni(vv,nv);
            }
        }
    }
    cout<<(aqt==0?"TAK\n":"NIE\n");
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T=1;
    cin>>T;
    while(T--) Inpt();
}