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<iostream>
#include<vector>
#include<algorithm>

#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)

using namespace std;

const int MAX = 100000;

int tc, N, M, K;

int A[MAX], U[MAX], V[MAX];
vector<int> E[MAX];
vector<int> G;

int P[MAX], C[MAX], X[MAX], Z[MAX], Y[MAX], W[MAX];
int sP, sC, pp, qq;

void dfscc(int i) {
	if (C[i] != -1) return;
	C[i] = sC;
	REP(j, E[i].size()) {
		int v = E[i][j];
		if (A[v] == pp || X[A[v]]) dfscc(v);
	}
}

vector<int> WW;

void dfsgg(int i) {
	if (qq != -1 && A[i] != qq && !X[A[i]]) return;
	if (W[i]) return;
	bool fp = false;
	if (!X[A[i]]) {
		G.push_back(i);	
		if (qq == -1) {			
			qq = A[i];
			WW.clear();
			fp = true;
		}
	}
	W[i] = 1;
	if (qq != -1) {
		WW.push_back(i);
	}
	REP(j, E[i].size()) {
		int v = E[i][j];
		if (!W[v]) dfsgg(v);
	}
	if (fp) {
		qq = -1;
		REP(j, WW.size()) W[WW[j]] = 0;
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> tc; REP(ixT, tc) {
		
		cin >> N >> M >> K;
		REP(i, N) { cin >> A[i]; A[i]--; E[i].clear(); }
		REP(i, M) { 
			cin >> U[i] >> V[i]; 
			U[i]--; V[i]--;
			E[U[i]].push_back(V[i]);
			E[V[i]].push_back(U[i]);
		}

		REP(i, K) P[i] = X[i] = 0;
		REP(i, N) C[i] = -1;
		sP = sC = 0;
		REP(i, N) if (C[i] == -1) { 
			pp = A[i]; dfscc(i); sC++;
			if (!P[pp]++) sP++; 
		}
				
		while (sP > 0) {			
			pp = -1;
			REP(i, K) if (P[i] == 1) { pp = i; break; }
			if (pp == -1) {
				break;
			}
			P[pp] = 0;
			sP--;
			X[pp] = 1;
						
			REP(i, N) { Z[i] = W[i] = 0; }
			REP(j, K) { Y[j] = -1; }
			G.clear(); qq = -1;
			REP(i, N) if (A[i] == pp) { 
				dfsgg(i); 
			}
						
			REP(j, G.size()) {
				int v = G[j];
				qq = A[v];		
				if (!X[qq] && C[v] != -1) {
					if (Z[C[v]]) {
						C[v] = Y[qq];
					} else {
						Z[C[v]] = 1;
						if (Y[qq] == -1) {
							Y[qq] = C[v];
						} else {
							P[qq]--;
							C[v] = Y[qq];
						}			
					}
				}
			}
			
		}
		cout << (sP == 0 ? "TAK" : "NIE") << endl;		
	}
	
	return 0;
}