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
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define VAR(v,w) __typeof(w) v=(w)
#define FORE(it,c) for(VAR(it,(c).begin());it!=(c).end();++it)
#define PB push_back
#define ALL(c) (c).begin(),(c).end()
#define SIZE(c) ((int)(c).size())
#define INT(x) int x; scanf("%d", &x)

typedef vector<int> VI;
typedef vector<VI> VVI;

VVI g;
int a[100000], cc[100000];
bool ex[100000];

void go(int v, int kk, int j) {
	FORE(it,g[v]) if ((a[*it] == kk && cc[*it] == -1) || (cc[*it] >= 0 && cc[*it] < j)) {
		cc[*it] = j;
		go(*it, kk, j);
	}
}

void oneCase() {
	INT(n);
	INT(m);
	INT(k);
	REP(i,n) {
		scanf("%d", &a[i]);
		--a[i];
	}
	g.clear();
	g.resize(n);
	REP(i,m) {
		INT(u);
		INT(v);
		--u;
		--v;
		g[u].PB(v);
		g[v].PB(u);
	}
	REP(j,k) ex[j] = 0;
	REP(i,n) ex[a[i]] = 1;
	VI p;
	REP(j,k) if (ex[j]) p.PB(j);
	do {
		REP(i,n) cc[i] = -1;
		bool bad = 0;
		REP(j,SIZE(p)) {
			bool found = 0;
			REP(i,n) if (a[i] == p[j] && cc[i] == -1) {
				if (found) {
					bad = 1;
					break;
				}
				cc[i] = j;
				go(i, a[i], j);
				found = 1;
			}
			if (bad) break;
		}
		if (!bad) {
			printf("TAK\n");
			return;
		}
	} while (next_permutation(ALL(p)));
	printf("NIE\n");
}

int main() {
	INT(t);
	REP(tt,t) oneCase();
}