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
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;

struct DSU {
    vi par, len;
    DSU (int n) : par(n), len(n,1) {
        iota(all(par),0);
    }
    int find(int u){
        if (par[u] == u) return u;
        return par[u] = find(par[u]);
    }
    int unite(int u, int v) {
        u = find(u), v = find(v);
        if (u==v) return 0;
        if (len[u] < len[v]) swap(u,v);
        par[v] = u;
        len[u] += len[v];
        return 1;
    }
};

void solve(){
    int n, m, k; cin >> n >> m >> k;

    DSU dsu(n);

    vvi bycol(k);
    vi col(n), colcnt(k);
    rep(i,0,n) {
        auto& c = col[i];
        cin >> c, --c, colcnt[c]++;
        bycol[c].push_back(i);
    }
    stack<int> todo;

    vvi adj(n);

    rep(i,0,m){
        int u,v; cin >> u >> v; --u,--v;
        adj[u].push_back(v);
        adj[v].push_back(u);

        if (col[u] == col[v]){
            colcnt[col[u]] -= dsu.unite(u, v);
        }
    }

    rep(i,0,k) if (colcnt[i] == 1) todo.push(i);

    vi lstbycol(k,-1);

    while(sz(todo)) {
        int curcol = todo.top(); todo.pop();
        if (colcnt[curcol] <= 0) continue;
        colcnt[curcol] = -1;

        for(auto at : bycol[curcol]){
            for(auto to : adj[at]) {
                if (lstbycol[col[to]] < 0){
                    lstbycol[col[to]] = to;
                }else{
                    int rem = dsu.unite(lstbycol[col[to]], to);
                    colcnt[col[to]] -= rem;
                    if (rem and colcnt[col[to]] == 1){
                        todo.push(to);
                    }
                }
            }
        }

        for(auto at : bycol[curcol]){
            for(auto to : adj[at]) {
                lstbycol[col[to]] = -1;
            }
        }
    }

    rep(i,0,k) if (colcnt[i] > 0) {
        cout << "NIE\n";
        return;
    }

    cout << "TAK\n";
}

int main(){
    cin.tie(NULL),ios::sync_with_stdio(false);
    
    int t; cin >> t;
    while(t--) solve();
}