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
#include <iostream>
#include <vector>
#include <queue>
#include <map>
//#define int long long
using namespace std;

int kol[100'007];
vector<int> tab[100'007];
int liczba[100'007][3];
int byo[10'007][10'007];

void cl(int n)
{
	for(int a=0; a<=n+3; a++)
		for(int i=0; i<=n+3; i++)
			byo[a][kol[i]]=0;
	for(int a=0; a<=n+3; a++)
	{
		kol[a]=0;
		tab[a].clear();
		for(int i=0; i<n+3; i++)
			liczba[a][i]=0;
	}
}


void solv()
{
	queue<pair<int,int> > lista;
	map<int,int> skala;
	int n, m, k, v, org, p, p2;
	cin>>n>>m>>k;
	
	for(int a=1; a<=n; a++){
		cin>>p;
		if(skala[p]==0)
			skala[p]=skala.size();
		kol[a]=skala[p];
	}
	
	for(int a=1; a<=n; a++){
		liczba[kol[a]][0]++;
		if(liczba[kol[a]][0]==1){
			liczba[kol[a]][1]=1;
			lista.push({a,kol[a]});
		}
	}
	for(int a=0; a<m; a++)
	{
		cin>>p>>p2;
		tab[p].push_back(p2);
		tab[p2].push_back(p);
	}
	
	while(!lista.empty()){
		v=lista.front().first;
		org=lista.front().second;
		lista.pop();
		if(byo[v][org]!=0)
			continue;
		if(kol[v]!=org && liczba[kol[v]][0]!=liczba[kol[v]][2])
			continue;
		byo[v][org]=1;
		
		if(kol[v]==org)
			liczba[org][2]++;
		for(unsigned int a=0; a<tab[v].size(); a++)
			lista.push({tab[v][a],org});
		
		if(liczba[org][0]==liczba[org][2] && liczba[org][1]!=0){
			liczba[org][1]=0;
			for(int a=1; a<=n; a++)
				if(kol[a]==org)
					for(unsigned int i=0; i<tab[a].size(); i++)
						for(int j=1; j<=n; j++)
							if(byo[tab[a][i]][kol[j]]!=0)
								lista.push({a,kol[j]});
			
		}
	}
	
	int fl=1;
	for(int a=1; a<=n; a++)
		if(liczba[kol[a]][0]!=liczba[kol[a]][2])
			fl=0;
	
	/*for(int a=1; a<=k; a++){
		for(int i=1; i<=n; i++)
			cout<<byo[i][a]<<" ";
		cout<<"\n";
	}*/
	
	if(fl==1)
		cout<<"TAK\n";
	else
		cout<<"NIE\n";
	
	cl(n);
}

int main()
{
	int n;
	cin>>n;
	for(int a=0; a<n; a++){
		solv();
	}
}