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
#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e5+5;

#define gc getchar_unlocked
inline int read(){
    int x=0; char c=gc();
    while(!isdigit(c))c=gc();
    while(isdigit(c))x=x*10+c-'0',c=gc();
    return x;
}

int n,m,k,a[N],vis[N];
vector<int> G[N],vec[N];
map<int,int> mp[N];
queue<int> Q;

void merge(int u,int v);
inline void upd(int u,int x,int y){
    if(mp[u].count(x))merge(mp[u][x],y);
    else mp[u][x]=y;
}

int fa[N],siz[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int u,int v){
    u=find(u),v=find(v);
    if(u==v)return;
    if(mp[u].size()<mp[v].size())swap(u,v);
    fa[v]=u,siz[u]+=siz[v];
    if(a[u]!=-1&&siz[u]==(int)vec[a[u]].size())Q.push(u);
    for(auto[x,y]:mp[v])if(~a[y])upd(u,x,y);
}

bool solve(){
    n=read(),m=read(),k=read();
    fill_n(vis+1,k,0),queue<int>().swap(Q);
    iota(fa+1,fa+1+n,1),fill_n(siz+1,n,1);
    for(int i=1;i<=n;i++)G[i].clear(),mp[i].clear();
    for(int i=1;i<=k;i++)vec[i].clear();
    for(int i=1;i<=n;i++)a[i]=read(),vec[a[i]].push_back(i);
    for(int i=1,u,v;i<=m;i++)u=read(),v=read(),G[u].push_back(v),G[v].push_back(u);
    for(int u=1;u<=n;u++)if(find(u)==u&&vec[a[u]].size()==1)Q.push(u);
    for(int u=1;u<=n;u++)for(int v:G[u])if(a[u]==a[v])merge(u,v);
    while(!Q.empty()){
        int x=Q.front(),i=a[x]; Q.pop();
        for(int u:vec[i])a[u]=-1;
        for(int u:vec[i])for(int v:G[u])if(~a[v]&&find(v)!=x)upd(x,a[v],v);
        for(int u:vec[i])for(int v:G[u])if(a[v]==-1)merge(u,v);
    }
    for(int i=1;i<=n;i++)if(~a[i])return false;
    return true;
}

int main(){
    int T=read();
    while(T--)puts(solve()?"TAK":"NIE");
    return 0;
}