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
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lb lower_bound
using namespace std;
int p[100007],ile[100007],skl[100007];
vector<int>gdzie[100007];
vector<int>g[100007];int timer=1;
void dfs(int v){
	skl[v]=timer;
	for(int e:g[v]){
		if(!skl[e]&&p[e]==p[v])dfs(e);
	}
}
struct dsu{
	vector<int>re,ra;
	dsu(int x,bool z){
		re.resize(x+1);
		if(z) ra.resize(x+1);
		for(int i=1;i<=x;i++)re[i]=i;
	}
	int Find(int x){
		if(re[x]==x)return x;
		re[x]=Find(re[x]);
		return re[x];
	}
	void Union(int u,int v,bool za){
		u=Find(u);v=Find(v);
		if(za&&ra[u]<ra[v])swap(u,v);
		re[v]=u;
		if(za)ra[u]++;
	}
};
void solve(){timer=1;
	int n,m,k,a,b;cin>>n>>m>>k;
	for(int i=0;i<=k;i++){gdzie[i].clear();ile[i]=0;}
	for(int i=1;i<=n;i++){g[i].clear();
		cin>>p[i];skl[i]=0;
		gdzie[p[i]].pb(i);
	}
	for(int i=0;i<m;i++){
		cin>>a>>b;g[a].pb(b);g[b].pb(a);
	}
	for(int i=1;i<=n;i++){
		if(!skl[i]){
			dfs(i);
			ile[p[i]]++;timer++;
		}
	}
	queue<int>q;
	dsu uzyte(n,0),czesci(timer-1,1);
	vector<unordered_map<int,int>>przylegle(n+1);
	vector<bool>uz(n+1);
	auto poloncz=[&](int r,int partia,int skladowa){
		skladowa=czesci.Find(skladowa);
		if(przylegle[r].find(partia)!=przylegle[r].end()){
			int pop=czesci.Find(przylegle[r][partia]);
			if(pop!=skladowa){
				czesci.Union(pop,skladowa,1);
				ile[partia]--;
				if(ile[partia]==1){
					q.push(partia);
				}
			}
		}
		przylegle[r][partia]=czesci.Find(skladowa);
	};
	for(int i=1;i<=k;i++)if(ile[i]==1){q.push(i);}
	while(!q.empty()){
		int aktp=q.front();q.pop();
		for(int e:gdzie[aktp]){
			uz[e]=1;
			for(int f:g[e]){
				if(uz[f]){
					int r1=uzyte.Find(e),r2=uzyte.Find(f);
					if(r1!=r2){
						if(przylegle[r1].size()<przylegle[r2].size())swap(r1,r2);
						for(auto e:przylegle[r2]){
							poloncz(r1,e.fi,e.se);
						}
						przylegle[r2].clear();
						uzyte.Union(r1,r2,0);
					}
				}
			}
		}
		for(int e:gdzie[aktp]){
			for(int f:g[e]){
				if(!uz[f]){
					int r=uzyte.Find(e);
					poloncz(r,p[f],skl[f]);
				}
			}
		}
	}
	bool wszystkie=1;
	for(int i=1;i<=n;i++){wszystkie&=uz[i];}
	cout<<(wszystkie?"TAK":"NIE")<<'\n';
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}