#include <bits/stdc++.h>
using namespace std;

int point[100010];
int sizes[100010];
int colour[100010];
set<pair<int, int>> neighbours[100010]; //<- (starting colour, index), can have repeats, can (and will) have itself as a neighbour

bool was_colour_painted[100010];

int CC_count[100010];

queue<int> united_vertices;

int search(int vertex) {
	if (point[vertex] == vertex) {
		return vertex;
	}
	point[vertex] = search(point[vertex]);
	return point[vertex];
}


void unite(int vertexa, int vertexb) {
	// assumes vertices have the same colour
	// or both have a painted colour
	// also assumes both are valid blobs of their colour -- CAREFUL IF USING THIS OTHERWISE

	// DELETE THESE
	/*
	assert(colour[vertexa] == colour[vertexb] || (was_colour_painted[colour[vertexa]] && was_colour_painted[colour[vertexb]]));
	if (was_colour_painted[colour[vertexa]]) {

		auto it = neighbours[vertexa].begin();
		int last_colour;
		if (it != neighbours[vertexa].end()) {
			last_colour = (*it).first;
			it++;
		}
		for (; it != neighbours[vertexa].end(); it++) {
			assert(last_colour != (*it).first);
		}
	}*/

	vertexa = search(vertexa);
	vertexb = search(vertexb);
	if (vertexa == vertexb) {
		return;
	}
	if (neighbours[vertexa].size() < neighbours[vertexb].size()) {
		swap(vertexa, vertexb);
	}

	sizes[vertexa] += sizes[vertexb];
	point[vertexb] = vertexa;

	//if (colour[vertexa] == -1) {
	//	for (auto it_a = neighbours[vertexa].begin(); it_a != vertexa)
		// Unite vertices with combining the lists, assuming both had at most 1 element and there were no elements of colour -1
	//}
	//else {
		// Does this lead to vertices being neighbours with themselves? Is that bad?
		// Definitely leads to repeat values also
	//}

	if (!was_colour_painted[colour[vertexa]]) {
		// Cost of this cannot be too bad -- we always add the shorter list to the larger one, and so with how union works this should be okay
		neighbours[vertexa].insert(neighbours[vertexb].begin(), neighbours[vertexb].end());
	}
	else {
		for (auto it = neighbours[vertexb].begin(); it != neighbours[vertexb].end(); it++) {
			int new_colour = (*it).first;
			int new_vertex = (*it).second;

			if (!was_colour_painted[new_colour]) {
				auto lb = neighbours[vertexa].lower_bound({new_colour, -1});
				auto ub = neighbours[vertexa].upper_bound({new_colour, 100010});
				if (lb == ub) {
					neighbours[vertexa].insert({new_colour, new_vertex});
				}
				else {
					// Calling unite in unite should be ok, since we are calling it on coloured vertices
					unite((*lb).second, new_vertex);
				}
			}
		}
	}


	if (!was_colour_painted[colour[vertexa]]) {
		CC_count[colour[vertexa]]--;
		if (CC_count[colour[vertexa]] == 1) {
			united_vertices.push(vertexa);
		}
	}
}

void colour_blank(int vertex) {
	vertex = search(vertex);

	was_colour_painted[colour[vertex]] = true;
	//cout << "Colouring colour " << colour[vertex] << " from vertex " << vertex << "\n";

	// unite neighbourhoods

	queue<pair<int, int>> pairs_to_unite;

	int last_colour = -2;
	int last_vertex = -1;
	bool seen_painted_colour = false;
	int last_painted_vertex = -1;

	set<pair<int, int>> new_neighbours;
	for (auto it = neighbours[vertex].begin(); it != neighbours[vertex].end(); it++) {
		int new_colour = (*it).first;
		int new_vertex = (*it).second;
		if (new_colour == last_colour) {
			pairs_to_unite.push({new_vertex, last_vertex});
		}
		else {
			if (!was_colour_painted[new_colour]) {
				new_neighbours.insert({new_colour, new_vertex});
			}
			else {
				if (seen_painted_colour) {
					pairs_to_unite.push({new_vertex, last_painted_vertex});
				}
				else {
					seen_painted_colour = true;
				}
				last_painted_vertex = new_vertex;
			}
		}
		last_colour = new_colour;
		last_vertex = new_vertex;
	}


	neighbours[vertex] = move(new_neighbours);

	if (seen_painted_colour) {

		// I think this may need to be done manually -- vertex is not really in a valid state rn
		pairs_to_unite.push({vertex, last_painted_vertex});
	}

	while (!pairs_to_unite.empty()) {
		auto x = pairs_to_unite.front();
		pairs_to_unite.pop();
		unite(x.first, x.second);
	}
}

void list_adjacency(int vertex_count) {
	for (int i = 1; i <= vertex_count; i++) {
		if (point[i] == i) {
			cout << "Vertex " << i << "\n";
			cout << "Colour: " << colour[i] << "\n";
			cout << "Neighbours:\n";
			for (auto it = neighbours[i].begin(); it != neighbours[i].end(); it++) {
				cout << "Colour " << (*it).first << " vertex " << (*it).second << "\n"; 
			}
			cout << "\n\n";
		}
	}
}

int main() {
	std::ios_base::sync_with_stdio(false);

	int t;
	cin >> t;
	for (int r = 0; r < t; r++) {
		united_vertices = {};
		int vertex_count, edge_count, colours;
		cin >> vertex_count >> edge_count >> colours;

		for (int i = 1; i <= colours; i++) {
			was_colour_painted[i] = false;
			CC_count[i] = 0;
		}

		for (int i = 1; i <= vertex_count; i++) {
			point[i] = i;
			sizes[i] = 1;
			cin >> colour[i];
			CC_count[colour[i]]++;
			neighbours[i].clear();
		}


		for (int i = 1; i <= vertex_count; i++) {
			if (CC_count[colour[i]] == 1) {
				united_vertices.push(i);
			}
		}

		for (int i = 0; i < edge_count; i++) {
			int a, b;
			cin >> a >> b;
			a = search(a);
			b = search(b);
			if (colour[a] == colour[b]) {
				unite(a, b);
			}
			else {
				neighbours[a].insert({colour[b], b});
				neighbours[b].insert({colour[a], a});
			}
		}

		while (!united_vertices.empty()) {
			int vertex = united_vertices.front();
			united_vertices.pop();
			//assert(CC_count[colour[vertex]] == 1);

			//list_adjacency(vertex_count);

			//cout << "Considering vertex " << vertex << "\nIt has colour " << colour[vertex] << " and points to " << point[vertex] << "\nIt has " << CC_count[colour[vertex]] << " CCs\n";

			vertex = search(vertex);
			colour_blank(vertex);
		}
		//list_adjacency(vertex_count);
		bool bad = false;
		for (int i = 1; i <= colours; i++) {
			if (!was_colour_painted[i] && CC_count[i] > 0) {
				bad = true;
			}
		}
		if (bad) {
			cout << "NIE\n";
		}
		else {
			cout << "TAK\n";
		}
	}
}