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
#include <bits/stdc++.h>
using namespace std;

int t, n, m, k;

struct DSU{
	vector<int> rep;
	vector<int> cnt;
	vector<bool> used;
	vector<map<int, int>> v;//ile jakich parti w komponencie
	queue<int> q;
	
	DSU(int n, int k, const vector<int> & vic, const vector<int> & tmp){
		rep.resize(n+1);
		v.resize(n+1);
		used.assign(k+1, false);
		cnt = tmp;
		
		for(int i = 1; i <= n; i++){
			rep[i] = i;
			v[i][vic[i]] = 1;
		}
	}
	
	int find(int x){
		if(rep[x] == x) return x;
		return rep[x] = find(rep[x]);
	}
	
	void merge(int a, int b){
		a = find(a);
		b = find(b);
		
		if(a == b) return;
		if(v[b].size() < v[a].size()) swap(a, b);
		
		
		rep[a] = b;
		for(auto [p, c]: v[a]){
			v[b][p] += c;
			if(v[b][p] == cnt[p] && !used[p]){
				q.push(p);
				used[p] = true;
			}
		}
		v[a].clear();
	}
	
};


void solve(){
	cin >> n >> m >> k;
	
	vector<vector<int>> g(n+1);
	vector<vector<int>> cities(k+1);//lista miast w ktorym wygrala partia i
	vector<int> cnt(k+1, 0);//ile wygrala partia i
	vector<int> vic(n+1);//jaka wygrala w miescie i
	
	//wczytywanko
	for(int i = 1; i <= n; i++){
		cin >> vic[i];
		cnt[vic[i]]++;
		cities[vic[i]].push_back(i);
	} 
	
	for(int i = 0; i < m; i++){
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	//warstwy od tylu
	DSU dsu(n, k, vic, cnt);
	
	//laczymy te same partie nieoddzielone przez inne
	for(int v = 1; v <= n; v++)
		for(auto u: g[v])
			if(vic[v] == vic[u] && v < u) dsu.merge(u, v);
			
	for(int i = 1; i <= n; i++){//wrzucamy na kolejke partie ktore sa cale scalone
		int v = dsu.find(i);
		int p = vic[i];
		
		if(dsu.v[v][p] == dsu.cnt[p] && !dsu.used[p]){
			dsu.q.push(p);
			dsu.used[p] = true;
		}
	}
	
	int cntP = 0;
	while(!dsu.q.empty()){
		int p = dsu.q.front(); dsu.q.pop();
		cntP++;
		
		for(auto v: cities[p])
			for(auto u: g[v]) dsu.merge(u, v);
	}
	
	int cntDistinctP = 0;
	for(int i = 1; i <= k; i++)
		if(cnt[i]) cntDistinctP++;
	
	
	if(cntDistinctP == cntP)cout<<"TAK\n";
	else cout << "NIE\n";
}

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	cin >> t;
	
	while(t--) solve();
}