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
#include <bits/stdc++.h>
using namespace std;

struct UF {
    int n;
    vector<int> par;
    UF(int _n) : n(_n) {
        for(int i = 0; i < n; i++) par.push_back(i);
    }
    int find(int a){
        if(a != par[a]) par[a] = find(par[a]);
        return par[a];
    }
    bool join(int a, int b){
        a = find(a);
        b = find(b);
        par[a] = b;
        return (a != b);
    }
};

void solve(){
	int N, M, K;
	cin >> N >> M >> K;
	vector<int> A(N);
	for(int& x : A){
		cin >> x; x--;
	}
	vector<vector<int> > where(K);
	vector<int> ncc(K);
	for(int i = 0; i < N; i++){
		where[A[i]].push_back(i);
		ncc[A[i]]++;
	}
	vector<vector<pair<int,int> >> adj(N);
	for(int i = 0; i < M; i++){
		int u, v;
		cin >> u >> v;
		u--; v--;
		adj[u].push_back({v, i});
		adj[v].push_back({u, i});
	}
	UF uf_within_color(N);


	UF blobs(M); // blobs are on edges
	vector<map<int, int> > blob_contents(M); // color -> representative

	for(int v = 0; v < N; v++){
		for(auto [w, e] : adj[v]){
			if(v > w) continue;
			blob_contents[e][A[v]] = v;
			blob_contents[e][A[w]] = w;
			if(A[v] == A[w]){
				if(uf_within_color.join(v, w)){
					ncc[A[v]]--;
				}
			}
		}
	}

	queue<int> to_delete;
	for(int c = 0; c < K; c++){
		if(ncc[c] == 1){
			to_delete.push(c);			
		}
	}
	while(!to_delete.empty()){
		int c = to_delete.front();
		to_delete.pop();
		for(int v : where[c]){
			int cur = -1;
			for(auto [w, e] : adj[v]){
				e = blobs.find(e);
				if(cur == -1){
					cur = e;
				} else if(cur == e){
					continue;
				} else {
					if(blob_contents[e].size() > blob_contents[cur].size()) swap(cur, e);
					for(auto [color, rep] : blob_contents[e]){
						if(!blob_contents[cur].count(color)){
							blob_contents[cur][color] = rep;
						} else {
							int prep = blob_contents[cur][color];
							if(uf_within_color.join(prep, rep)){
								ncc[color]--;
								if(ncc[color] == 1){
									to_delete.push(color);
								}
							}
						}
					}
					blobs.join(e, cur);
				}
			}
		}
	}
	int works = true;
	for(int c = 0; c < K; c++) if(ncc[c] > 1) works = false;
	cout << (works ? "TAK" : "NIE") << '\n';
}

int main(){
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int T;
	cin >> T;
	while(T--) solve();
}