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
#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<long long, long long>
using namespace std;
using ll = long long;
using ld = long double;

constexpr int SIZE = 1e5+5;

vector<int> graph[SIZE];
vector<int> nodes[SIZE];
int col[SIZE];
int fu[SIZE];
int siz[SIZE];
bool done[SIZE];
vector<pii> cons;
queue<int> Q;

int FIND(int a){
	if (fu[a] != a) fu[a] = FIND(fu[a]);
	return fu[a];
}

void UNION(int a, int b){
	int A = FIND(a);
	int B = FIND(b);
	if (A == B) return;

	if (siz[B] > siz[A]) swap(A, B);

	siz[A] += siz[B];
	fu[B] = A;

	if (siz[A] == (int)nodes[col[A]].size()) Q.push(col[A]);
}

int SOLVE(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

	int n, m, k;
	cin >> n >> m >> k;

	for (int i=1; i<=n; i++){
		graph[i].clear();
		fu[i] = i;
		siz[i] = 1;
	}
	for (int i=1; i<=k; i++){
		nodes[i].clear();
		done[i] = 0;
	}


	for (int i=1; i<=n; i++){
		cin >> col[i];
		nodes[col[i]].push_back(i);
	}

	int a, b;

	for (int i=0; i<m; i++){
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);

		if (col[a] != col[b]) continue;
		UNION(a, b);
	}

	for (int i=1; i<=n; i++) {
		a = FIND(i);
		if (siz[a] == 1 && (int)nodes[col[a]].size() == 1) Q.push(col[a]);
	}

	while (!Q.empty()){
		a = Q.front();
		Q.pop();

		if (done[a]) continue;
		done[a] = 1;
		cons.clear();

		for (int v:nodes[a]){
			for (int u:graph[v]){
				if (done[col[u]]) continue;
				cons.push_back({col[u], u});
			}
		}

		sort(cons.begin(), cons.end());

		int sz = cons.size();
		
		for (int i=1; i<sz; i++){
			if (cons[i-1].F != cons[i].F) continue;
			UNION(cons[i-1].S, cons[i].S);
		}
	}

	for (int i=1; i<=k; i++){
		if (done[i] || nodes[i].empty()) continue;
		cout << "NIE\n";
		return 0;
	}

	cout << "TAK\n";
	return 0;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
	cin >> t;
	while (t--) SOLVE();
	
return 0;}