#include <bits/stdc++.h>
using namespace std;
const bool DEBUG = !true;
struct Town {
	int winner = 0;
	set<int> neighbours;
	bool removed = false;
};

void printTowns(const vector<Town> &towns) {
	if (!DEBUG) {
		return;
	}
	for (size_t i = 1; i < towns.size(); ++i) { // assuming 1-based indexing
		if (towns[i].removed) {
			continue;
		}
		cout << "Town " << i << ":\n";
		cout << "  Winner: " << towns[i].winner << " removed: "
				<< (towns[i].removed ? "removed" : "existing") << "\n";
		cout << "  Neighbours: ";

		if (towns[i].neighbours.empty()) {
			cout << "(none)";
		} else {
			cout << "{ ";
			for (int n : towns[i].neighbours) {
				cout << n << " ";
			}
			cout << "}";
		}
		cout << "\n\n";
		cout.flush(); // flush after each town
	}
	cout.flush(); // final flush (optional but explicit)
}

void printVector(const vector<int> &v, const string &label = "") {
	if (!DEBUG) {
		return;
	}
	if (!label.empty()) {
		cout << label << "\n";
	}

	cout << "[ ";
	for (int x : v) {
		cout << x << " ";
	}
	cout << "]";
	cout << "\n";
	cout.flush();
}

void printSet(const set<int> &s, const string &label = "") {
	if (!DEBUG) {
		return;
	}
	if (!label.empty()) {
		cout << label << "\n";
	}

	cout << "{ ";
	for (int x : s) {
		cout << x << " ";
	}
	cout << "}";
	cout << "\n";
	cout.flush();
}

struct Finder {
	const int k;
	vector<Town> towns;

	Finder(const vector<Town> &towns, int k) :
			k(k), towns(towns) {
	}

	void process() {

		set<int> notRemovedParts;
		for (Town t : towns) {
			notRemovedParts.insert(t.winner);
		}
		notRemovedParts.erase(0);

		bool stopped = false;
		do {
			printSet(notRemovedParts, "notRemovedParts");
			stopped = false;
			for (int partToCheck : notRemovedParts) {
				vector<int> subGraph = getConnectedComponent(partToCheck);
				if (!subGraph.empty()) {
					printVector(subGraph, "group ");
					stopped = true;
					extractComponent(subGraph);
					printTowns(towns);
					notRemovedParts.erase(partToCheck);
					break;
				}
			}
		} while (stopped);
		if (notRemovedParts.empty()) {
			cout << "TAK" << endl;
		} else {
			cout << "NIE" << endl;
		}
	}
	void extractComponent(const vector<int> &comp) {
		if (comp.empty())
//			return {};
			return;

		set<int> compSet(comp.begin(), comp.end());
		set<int> boundary; // all neighbors outside the component

		// Collect all boundary nodes
		for (int u : comp) {
			if (towns[u].removed) {
				continue;
			}

			for (int v : towns[u].neighbours) {
				if (!compSet.count(v) && !towns[v].removed) {
					boundary.insert(v);
				}
			}
		}

		// Connect all boundary nodes with each other
		if (boundary.size() > 0) {
			vector<int> boundaryVec(boundary.begin(), boundary.end());
//			for (int i = 0; i < (int) boundaryVec.size(); ++i) {
//				for (int j = i + 1; j < (int) boundaryVec.size(); ++j) {
//					towns[boundaryVec[i]].neighbours.insert(boundaryVec[j]);
//					towns[boundaryVec[j]].neighbours.insert(boundaryVec[i]);
//				}
//			}

			set<int> p;
			vector<int> hubs;
			for (int b : boundaryVec) {
				if (p.count(b) == 0) {
					p.insert(b);
					hubs.push_back(b);
				}
			}
			for (int i = 0; i < (int) hubs.size(); ++i) {
				for (int j = i + 1; j < (int) boundaryVec.size(); ++j) {
					towns[hubs[i]].neighbours.insert(boundaryVec[j]);
					towns[boundaryVec[j]].neighbours.insert(hubs[i]);
				}
			}

//			for (int i = 1; i < (int) boundaryVec.size(); i++) {
//				towns[hub].neighbours.insert(boundaryVec[i]);
//				towns[boundaryVec[i]].neighbours.insert(hub);
//			}
		}
		// Remove component nodes
		for (int u : comp) {
			if (towns[u].removed)
				continue;

			for (int v : towns[u].neighbours) {
				towns[v].neighbours.erase(u);
			}

			towns[u].neighbours.clear();
			towns[u].removed = true;
		}

//		return comp;
	}
	vector<int> getConnectedComponent(int value) {
		vector<int> nodes;

		// collect nodes with given winner
		for (int i = 1; i < (int) towns.size(); ++i) {
			if (towns[i].winner == value) {
				nodes.push_back(i);
			}
		}

		if (nodes.empty())
			return {}; // no such nodes

		// BFS
		vector<bool> allowed(towns.size(), false);
		for (int x : nodes) {
			allowed[x] = true;
		}
		vector<bool> visited(towns.size(), false);
		queue<int> q;

		q.push(nodes[0]);
		visited[nodes[0]] = true;

		unsigned int count = 1;
		while (!q.empty()) {
			int u = q.front();
			q.pop();
			for (int v : towns[u].neighbours) {
				if (allowed[v] && !visited[v]) {
					visited[v] = true;
					q.push(v);
					count++;
				}
			}
		}

		// check connectivity
		if (count != nodes.size()) {
			return {}; // not connected
		}

		return nodes; // connected, return all indices
	}
};

int main() {
//	ifstream cin("tests/0a.in");
	// ifstream cin("D:/cpp/_tests/3b-kam/1.in");
//	 ifstream cin("D:/cpp/_tests/3b-kam/93242_kam_tests/small/kam1.in");
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	int t, u, v;
	cin >> t;
	for (int i = 0; i < t; i++) {
		int n, m, k;
		cin >> n;
		cin >> m;
		cin >> k;
		vector<Town> towns(n + 1);
		for (int j = 1; j <= n; j++) {
			cin >> towns[j].winner;
		}
		for (int j = 0; j < m; j++) {
			cin >> u;
			cin >> v;
			towns[u].neighbours.insert(v);
			towns[v].neighbours.insert(u);
		}

		printTowns(towns);
		Finder f(towns, k);
		f.process();
	}
}