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
129
130
131
132
133
134
135
136
137
#include <bits/stdc++.h>
int T,N,M,K,a[100009],v[100009],pa[100009],aa[100009],
bb[100009],rt[100009],ls[4000009],rs[4000009],sg[4000009],kk,pa2[100009];
std::vector<int> t[100009],t2[100009];
std::queue<int> q;
//std::set<int> ss[100009];
#define md ((l+r)>>1)
inline int fr(int x) {
    while(x!=pa[x]) x=pa[x]=pa[pa[x]];
    return x;
}
inline int fr2(int x) {
    while(x!=pa2[x]) x=pa2[x]=pa2[pa2[x]];
    return x;
}
inline void tr(int x,int y) {
	assert(a[x]==a[y]);
	if(v[a[x]]==0) return;
	int p1=fr2(x),p2=fr2(y);
	if(p1!=p2) {
		pa2[p1]=p2;
		v[a[x]]--;
		if(v[a[x]]==1) q.push(a[x]);
	}
}
void up(int& n,int l,int r,int p,int v) {
    if(n==0) {
    	n=++kk;ls[n]=rs[n]=sg[n]=0;
    }
    if(l==r) {
    	if(sg[n]) tr(sg[n],v);
    	else sg[n]=v;
    	return;
    }
    if(p<=md) up(ls[n],l,md,p,v);
    else up(rs[n],md+1,r,p,v);
}
void mg(int& x,int y,int l,int r) {
    if(x==0||y==0) {
        x+=y;
        return;
    }
    if(l==r) {
    	tr(sg[x],sg[y]);
        return;
    }
    mg(ls[x],ls[y],l,md),mg(rs[x],rs[y],md+1,r);
}

inline void co(int x,int y) {
    x=fr(x);y=fr(y);
    if(x==y) return;
//    if(ss[x].size()<ss[y].size()) {
//        std::swap(x,y);
//    }
    mg(rt[x],rt[y],1,K);
//    for(auto it=ss[y].begin();it!=ss[y].end();it++) {
//        int p=(*it);
//        auto it2=ss[x].find(p);
//        if(it2==ss[x].end()){
//            ss[x].insert(p);
//        } else {
//            v[p]--;
//            if(v[p]==1) q.push(p);
//        }
//    }
    pa[y]=x;
}
signed main(void) {
    scanf("%d",&T);
    while(T--) {
        scanf("%d %d %d",&N,&M,&K);
        for(int i=1;i<=K;i++) {
            v[i]=0;
            t2[i]=t2[0];
        }
        kk=0;
        for(int i=1;i<=N;i++) pa2[i]=i;
        for(int i=1;i<=N;i++) {
            scanf("%d",&a[i]);
//            assert(1<=a[i]&&a[i]<=K);
            rt[i]=0;
            v[a[i]]++;
            t2[a[i]].push_back(i);
        }
        for(int i=1;i<=K;i++) {
            if(v[i]==1) q.push(i);
        }
        for(int i=1;i<=N;i++) {
            t[i]=t[0];
            pa2[i]=i;
            pa[i]=i;
        }
        for(int i=1;i<=M;i++) {
            scanf("%d %d",&aa[i],&bb[i]);
            t[aa[i]].push_back(bb[i]);
            t[bb[i]].push_back(aa[i]);
        }
        for(int i=1;i<=M;i++) {
            if(a[aa[i]]==a[bb[i]]) {
            	tr(aa[i],bb[i]);
            }
        }
        while(!q.empty()) {
            int x=q.front();
            q.pop();
            v[x]=0;
            for(int i=0;i<t2[x].size();i++) {
                int p=t2[x][i];
                for(int j=0;j<t[p].size();j++) {
                	int tt=a[t[p][j]];
                	if(v[tt]==0) continue;
                	up(rt[p],1,K,tt,t[p][j]);
//                    co(fr(p),fr(t[p][j]));
                }
            }
            for(int i=0;i<t2[x].size();i++) {
                int p=t2[x][i];
                for(int j=0;j<t[p].size();j++) {
                	int tt=a[t[p][j]];
                	if(v[tt]==0) {
                		co(p,t[p][j]);
                	}
                }
            }
        }
        bool gg=0;
        for(int i=1;i<=K;i++) {
            if(v[i]) gg=1;
        }
        if(gg) {
            printf("NIE\n");
        } else {
            printf("TAK\n");
        }
    }
}