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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back
#define fi first
#define se second
#define each(a,x) for(auto &a:x)
#define vi vector<int>
#define vll vector<ll>
#define vull vector<ull>
#define pi pair<int,int>
#define pll pair<ll,ll>
#define nl '\n'
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx2")
#pragma GCC target("bmi")
#pragma GCC target("bmi2")
#pragma GCC target("lzcnt")
#pragma GCC target("popcnt")
const int N = 5e5+1234,INF = 2e9+1234,mod = 1e9+7;
const ll INF_L = (ll)2e18+1234;
int n,m,k;
int A[N],B[N],C[N];
vector<int> rep,IL,ILR;
vector<pair<int,int>> D;
vector<vector<int>> G;
vector<bool> uzyte;
vector<map<int,int>> VV;
int findd(int v)
{
    if(rep[v]==v) return v;
    rep[v]=findd(rep[v]);
    return rep[v];
}
void unionnn(int x, int y)
{
    x=findd(x),y=findd(y);if(x==y)return;
    rep[x]=y;
}
void unionn(int x, int y)
{
    x=findd(x),y=findd(y);if(x==y)return;
    --IL[A[x]],ILR[A[x]]=y,rep[x]=y;
    if(IL[A[x]]==1) D.pb({A[x],ILR[A[x]]});
}
vector<pair<int,int>> rep2;
int findd2(int v)
{
    if(rep2[v].first==v) return v;
    rep2[v].first=findd2(rep2[v].first);return rep2[v].first;
}
void unionn2(int x, int y)
{
    x=findd2(x),y=findd2(y);if(x==y) return;
    if(VV[rep2[x].second].size()>VV[rep2[y].second].size()) swap(x,y);
    for(auto it=VV[rep2[x].second].begin();it!=VV[rep2[x].second].end();++it)
    {
        if(auto it2=VV[rep2[y].second].find(it->first)==VV[rep2[y].second].end())
        {
            VV[rep2[y].second][it->first]=it->second;
        }
        else
        {
            unionn(it->second,VV[rep2[y].second][it->first]);
        }
    }
    rep2[x].first=y;
}
void solve()
{
    D.clear();rep.clear();IL.clear();ILR.clear();uzyte.clear();
    cin>>n>>m>>k;
    for(int i=1;i<=n;++i)cin>>A[i];
    rep(i,m)cin>>B[i]>>C[i]; 
    G.assign(n+1,{});rep(i,m) G[B[i]].pb(C[i]),G[C[i]].pb(B[i]);
    rep.assign(n+1,0);for(int i=1;i<=n;++i)rep[i]=i;
    rep(i,m) if(A[B[i]]==A[C[i]]) unionnn(B[i],C[i]); 
    IL.assign(k+1,0);ILR.assign(k+1,0);for(int i=1;i<=n;++i) if(rep[i]==i)++IL[A[i]],ILR[A[i]]=i;
    for(int i=1;i<=k;++i) if(IL[i]==1) D.pb({i,ILR[i]});
    vector<vector<int>>uz;uz.assign(k+1,{});for(int i=1;i<=n;++i) uz[A[i]].pb(i);
    int succ=0;for(int i=1;i<=k;++i) if(!uz[i].empty()) ++succ;
    uzyte.assign(k+1,0);rep2.assign(n+1,{0,0});VV.assign(n+1,{});
    rep(zz,succ)
    {
        if(D.empty()){cout << "NIE" << nl;return;}
        pair<int,int> akt=D.back();D.pop_back();uzyte[akt.first]=1;map<int,int> M;
        //cout << "akt.fi: " << akt.first << endl;
        for(auto v:uz[akt.first])
        {
            for(auto x:G[v])
            {
                if(uzyte[A[x]] or rep[v]==rep[x]) continue;
                if(auto it=M.find(A[x])==M.end()) M[A[x]]=findd(x);
                else unionn(findd(x),M[A[x]]);
            }
        }
        for(auto v:uz[akt.first]) rep2[v].first=uz[akt.first].back();
        VV[uz[akt.first].back()]=M,rep2[uz[akt.first].back()].second=uz[akt.first].back();
        for(auto v:uz[akt.first])
        {
            for(auto x:G[v])
            {
                if(rep2[x].first==0 or rep2[v].first==rep2[x].first) continue;
                unionn2(v,x);
            }
        }
    }
    cout << "TAK" << nl;
}
int main()
{ 
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    cin >> T;
    while(T--) solve();
    return 0;
}