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
#ifdef LOC
#include "debuglib.hpp"
#else
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define deb(...)
#define DBP(...)
#endif
using namespace std;
using   ll         = long long;
using   vi         = vector<int>;
using   pii        = pair<int, int>;
#define pb           push_back
#define mp           make_pair
#define x            first
#define y            second
#define rep(i, b, e) for (int i = (b); i < (e); i++)
#define each(a, x)   for (auto& a : (x))
#define all(x)       (x).begin(), (x).end()
#define sz(x)        int((x).size())

int n, m, k;
vector<vi> adj, group;
vector<map<int, int>> neigh;
vi col, cnt, id, ready;

void join(int u, int v);

void addNeigh(int g, int v) {
	assert(col[g] == -1);
	if (col[v] != -1) {
		int& e = neigh[id[g]][col[v]];
		if (e > 0) join(e-1, v);
		e = v+1;
	}
}

void join(int u, int v) {
	assert(col[u] == col[v]);
	u = id[u]; v = id[v];
	if (u == v) return;

	if (sz(group[u]) < sz(group[v])) swap(u, v);
	group[u].insert(group[u].end(), all(group[v]));
	each(e, group[v]) id[e] = u;

	if (col[u] == -1) {
		if (sz(neigh[u]) < sz(neigh[v])) swap(neigh[u], neigh[v]);
		each(e, neigh[v]) addNeigh(u, e.y-1);
	} else if (sz(group[u]) == cnt[col[u]]) {
		ready.pb(u);
	}
}

void upgrade(int v) {
	assert(col[v] != -1);
	v = id[v];
	auto tmp = group[v];
	each(u, tmp) col[u] = -1;
	each(u, tmp) each(e, adj[u]) addNeigh(v, e);
	each(u, tmp) each(e, adj[u]) if (col[e] == -1) join(v, e);
}

void run() {
	cin >> n >> m >> k;

	int existingColors = 0;
	adj.assign(n, {});
	neigh.assign(n, {});
	col.assign(n, 0);
	cnt.assign(k, 0);
	ready.clear();
	id.resize(n);
	iota(all(id), 0);
	group.assign(n, {});
	rep(i, 0, n) group[i].pb(i);

	rep(i, 0, n) {
		cin >> col[i];
		col[i]--;
		existingColors += (cnt[col[i]]++ == 0);
	}

	rep(i, 0, m) {
		int u, v;
		cin >> u >> v;
		u--; v--;
		adj[u].pb(v);
		adj[v].pb(u);
		if (col[u] == col[v]) join(u, v);
	}

	rep(i, 0, n) if (cnt[col[i]] == 1) {
		ready.pb(i);
	}

	rep(i, 0, sz(ready)) {
		upgrade(ready[i]);
	}

	cout << (sz(ready) == existingColors ? "TAK\n" : "NIE\n");
}

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--) run();
}