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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <bits/stdc++.h>
using namespace std;

struct Test {
void solve(int nr) {
	int n, m;
	int k; // number of types
	cin >> n >> m >> k;
	if (n == -1) {
		cout << "BAD " << nr << endl;
		exit(0);
	}
	vector<int> type(n + 1);
	vector<vector<int>> those(k + 1);
	vector<vector<int>> edges(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> type[i];
		those[type[i]].push_back(i);
	}
	vector<int> g(n+1);
	vector<vector<int>> inv(n+1);
	vector<map<int,int>> nei(n+1); // nei[g][type] = id of one of my neighbours of this type
	for (int i = 1; i <= n; i++) {
		g[i] = i;
		inv[i] = {i};
	}
	vector<int> q;
	vector<bool> pushed(k+1);
	vector<pair<int,int>> waiting_uni;
	
	auto uni = [&](int x, int y) {
		// assert(type[x] == type[y] || (pushed[type[x]] && pushed[type[y]]));
		// cout << x << " " << y << endl;
		x = g[x];
		y = g[y];
		if (x == y) {
			return;
		}
		if (inv[x].size() > inv[y].size()) {
			swap(x, y);
		}
		for (int a : inv[x]) {
			inv[y].push_back(a);
			g[a] = y;
		}
		if (pushed[type[inv[x][0]]]) {
			auto cp = nei[x];
			for (pair<int,int> p : cp) {
				auto it = nei[y].find(p.first);
				if (it == nei[y].end()) {
					nei[y][p.first] = p.second;
				}
				else {
					if (g[p.second] != g[it->second]) {
						waiting_uni.emplace_back(p.second, it->second);
					}
				}
			}
		}
		inv[x].clear();
		nei[x].clear();
		int t = type[inv[y][0]];
		if (!pushed[t] && inv[y].size() == those[t].size()) {
			// for (int a : inv[y]) {
				// assert(type[a] == t);
			// }
			pushed[t] = true;
			q.push_back(t);
		}
	};
	
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		if (type[a] == type[b]) {
			waiting_uni.emplace_back(a, b);
		}
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	for (int t = 1; t <= k; t++) {
		if ((int) those[t].size() == 1) {
			pushed[t] = true;
			q.push_back(t);
		}
	}
	while (!q.empty() || !waiting_uni.empty()) {
		if (!waiting_uni.empty()) {
			pair<int,int> p = waiting_uni.back();
			waiting_uni.pop_back();
			uni(p.first, p.second);
			continue;
		}
		assert(!q.empty());
		int t = q.back();
		q.pop_back();
		for (int a : those[t]) {
			for (int b : edges[a]) {
				if (pushed[type[b]]) {
					if (g[a] != g[b]) {
						waiting_uni.emplace_back(a, b);
					}
				}
				else {
					auto it = nei[g[a]].find(type[b]);
					if (it == nei[g[a]].end()) {
						nei[g[a]][type[b]] = b;
						// cout << ">>>> " << a << " " << b << endl;
					}
					else {
						waiting_uni.emplace_back(b, it->second);
					}
				}
			}
		}
	}
	// for (int a = 1; a <= n; a++) {
		// if (!inv[a].empty()) {
			// for (int x : inv[a]) cout << x << ",";
			// cout << "   ";
			// for (pair<int,int> p : nei[a]) cout << "(" << p.first << "," << p.second << ") ";
			// cout << endl;
		// }
	// }
	for (int a = 1; a <= n; a++) {
		if (!pushed[type[a]]) {
			cout << "NIE\n";
			return;
		}
	}
	cout << "TAK\n";
}
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	for (int nr = 1; nr <= T; nr++) {
		Test test;
		test.solve(nr);
	}
}