#include<bits/stdc++.h>

using namespace std;

int LOST_MEM = 0;

struct Cci {
	unordered_set<int> c;
};

struct Ca {
	unordered_map<int, Cci*> adj;
	unordered_set<int> elems;
	int total = 0;
};

Cci* mergeCci(vector<Cci*>& comps, int x, int y) {
	
	if (comps[x]->c.size() < comps[y]->c.size()) {
		return mergeCci(comps, y, x);
	}
	
	if (comps[x] == comps[y]) {
		return comps[x];
	}
				
	for (int elem : comps[y]->c) {
		comps[x]->c.insert(elem);
		comps[elem] = comps[x];
	}
	
	return comps[x];
}

Ca* mergeCa(Ca* ca1, Ca* ca2, vector<Ca*>& fcomps, vector<vector<int>>& cities, queue<int>& q, vector<bool>& visited, vector<Cci*>& comps) {
	if (ca1->total < ca2->total) {
		return mergeCa(ca2, ca1, fcomps, cities, q, visited, comps);
	}
	
	if (ca1 == ca2) {
		return ca1;
	}
	
	for (auto elem: ca2->elems) {
		if (ca1->elems.find(elem) == ca1->elems.end()) {
			ca1->total += 1;
			ca1->elems.insert(elem);
		}
	}
	
	for (auto& cs : ca2->adj) {
		Cci* ci = cs.second;
		int pty = cs.first;
		if (ca1->adj.find(pty) == ca1->adj.end()) {
			ca1->adj[pty] = ci;
			ca1->total += 1;
		} else {
			Cci* ci1 = ca1->adj.at(pty);
			int ind1 = *(ci1->c.begin());
			int ind2 = *(ci->c.begin());
			mergeCci(comps, ind1, ind2);
			if (!visited[pty] && comps[ind1]->c.size() == cities[pty].size()) {
				visited[pty] = true;
				q.push(pty);
			}
		}
	}
	
	for (int elem : ca2->elems) {
		fcomps[elem] = ca1;
	}
	
	return ca1;
}

bool woj() {
	int n, m, k;
	cin >> n >> m >> k;
	
	
	vector<vector<int>> edges(n);
	
	vector<int> winners(n);
	
	vector<vector<int>> cities(k, vector<int>());
	
	vector<Cci*> comps(n);
	
	vector<Ca*> fcomps(n);
	
	for (int i = 0; i < n; i++) {
		fcomps[i] = new Ca();
	}
	
	vector<bool> visited(k, false);
	
	for (int i = 0; i < n; i++) {
		int w;
		cin >> w;
		winners[i] = w - 1;
		cities[w - 1].push_back(i);
		comps[i] = new Cci();
		comps[i]->c = {i};
	}

	
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		if (u == v) {
			continue;
		}
		edges[u-1].push_back(v-1);
		edges[v-1].push_back(u-1);
		
		if (winners[u-1] == winners[v-1]) {
			mergeCci(comps, u-1, v-1);
		}
	}
	
	queue<int> toRemove;
	
	for (int i = 0; i < n; i++) {
		if (!visited[winners[i]] && comps[i]->c.size() == cities[winners[i]].size()) {
			visited[winners[i]] = true;
			toRemove.push(winners[i]);
		}
	}
	
	while (!toRemove.empty()) {
		int pt = toRemove.front();
		toRemove.pop();
						
		unordered_set<Ca*> cas_to_merge;
		Ca* new_ca = fcomps[cities[pt][0]];
		
		for (int i = 0; i < cities[pt].size(); i++) {
			for (int j = 0; j < (int) edges[cities[pt][i]].size(); j++) {
				int nbr = edges[cities[pt][i]][j];
				if (fcomps[nbr]->total != 0) {
					cas_to_merge.insert(fcomps[nbr]);
					continue;
				}
				
				int nbrpt = winners[nbr];
				Cci* nbrcci = comps[nbr];
				
				if (new_ca->adj.find(nbrpt) == new_ca->adj.end()) {
					new_ca->adj[nbrpt] = comps[nbr];
					new_ca->total += 1;
				} else {
					int other = *(new_ca->adj.at(nbrpt)->c.begin());
					Cci* merged_cci = mergeCci(comps, nbr, other);
					if (!visited[nbrpt] && merged_cci->c.size() == cities[nbrpt].size()) {
						toRemove.push(nbrpt);
						visited[nbrpt] = true;
					}
				}
			}
		}
	
		new_ca->total += cities[pt].size();
		
		for (int i = 0; i < cities[pt].size(); i++) {
			new_ca->elems.insert(cities[pt][i]);
			fcomps[cities[pt][i]] = new_ca;
		}
		
		if (cas_to_merge.empty()) {
			for (auto& elem: new_ca->adj) {
				if (!visited[elem.first] && elem.second->c.size() == cities[elem.first].size()) {
					visited[elem.first] = true;
					toRemove.push(elem.first);
				}
			}
		}
		
		
		stack<Ca*> cas_stack;
		cas_stack.push(new_ca);
		for (Ca* elem : cas_to_merge) {
			cas_stack.push(elem);
		}
		
		while (cas_stack.size() > 1) {
			Ca* ca1 = cas_stack.top();
			cas_stack.pop();
			Ca* ca2 = cas_stack.top();
			cas_stack.pop();
			Ca* merged_ca = mergeCa(ca1, ca2, fcomps, cities, toRemove, visited, comps);
			cas_stack.push(merged_ca);
		}
		
		Ca* final_ca = cas_stack.top();
		if (final_ca->adj.find(pt) != final_ca->adj.end()) {
			final_ca->total -= 1;
			final_ca->adj.erase(pt);
		}
		cas_stack.pop();
	}
	
	bool is_ok = true;
	
	int num_wrong = 0;
	
	for (int i = 0; i < k; i++) {
		if (!visited[i] && cities[i].size() > 0) {
			is_ok = false;
			break;
		} 
	}
	
		
	return is_ok;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
			
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		bool result = woj();
		if (result) {
			cout << "TAK\n";
		} else {
			cout << "NIE\n";
		}
		cout.flush();
	}		

}