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
123
124
125
126
127
128
129
130
131
132
#include<bits/stdc++.h>

using namespace std;

int f(int a, vector<int> &P){
    if(a == P[a]) return a;
    return P[a] = f(P[a], P);
}

void onion(int u, int v, vector<int> &P, vector<int> &S, vector<int> &cnt, vector<int> &C, queue<int> &Q, vector<bool> &V){
    //cerr << "u " << u << " " << "v " << v << "\n";
    if(S[P[u]] < S[P[v]]) swap(u, v);
    S[P[u]] += S[P[v]];
    P[P[v]] = P[u];
    //cerr << C[v] << "\n";
    if(C[v] < 0) return;
    cnt[C[v]]--;
    // //cerr << "coutn " << cnt[C[v]] << "\n";
    if(cnt[C[v]] < 2 && !V[C[v]]){
        Q.push(C[v]);
        V[C[v]] = true;
    }
}

void add(int v, unordered_map<int, int> &V, vector<int> &P, vector<int> &S, queue<int> &Q, vector<int> &cnt, vector<int> &C, vector<bool> &B){
    auto it = V.find(C[v]);
    if(it == V.end()){
        V[C[v]] = P[v];
        return;  
    }
    if(f(v, P) == f(V[C[v]], P)) return;
    onion(v, V[C[v]], P, S, cnt, C, Q, B);
}

void merge(int u, int v, vector<unordered_map<int, int>> &M, vector<int> &NP, vector<int> &NS, vector<int> &I, vector<int> &P, vector<int> &S, queue<int> &Q, vector<int> &cnt, vector<int> &C, vector<bool> &V){
    //cerr << M[I[NP[u]]].size() << " " << M[I[NP[v]]].size() << "\n";
    if(M[I[NP[u]]].size() < M[I[NP[v]]].size()) swap(I[NP[u]], I[NP[v]]);
    for(auto a : M[I[NP[v]]]) add(a.second, M[I[NP[u]]], P, S, Q, cnt, C, V);
    //for(auto it:M[I[NP[u]]]) cerr << it.first << " " << it.second << " ";
    //cerr << "\n";
    if(NS[NP[u]] < NS[NP[v]]) swap(u, v);
    NS[NP[u]] += NS[NP[v]];
    NP[NP[v]] = NP[u];
}

bool check(const vector<vector<int>> &G, queue<int> &Q, const vector<vector<int>> &W, vector<int> &C, vector<int> &P, vector<int> &S, vector<int> &cnt, vector<bool> &V){
    vector<int> NS(G.size(), 1);
    vector<int> NP(G.size());
    for(int i=0; i<G.size(); i++) NP[i] = i;
    vector<unordered_map<int, int>> M;
    vector<int> I(G.size());
    int k = cnt.size();
    for(int i=1; i<k; i++){
        if(Q.empty()) return false;
        //if(i == k-1) return true;
        int c = Q.front();
        Q.pop();
        //cerr << i << " " << "c: " << c+1 << "\n";
        for(auto v:W[c]) C[v] = -1;
        for(auto v:W[c]){
            unordered_map<int, int> mapa;
            M.push_back(mapa);
            I[v] = M.size()-1;
            for(auto u:G[v]){
                //cerr << "v: " << v+1 << " " << u+1 << "\n";
                int p = f(v, NP);
                if(C[u] < 0 && f(u, NP) != p && I[v] != I[u]) merge(u, v, M, NP, NS, I, P, S, Q, cnt, C, V);
                else if(C[u] >= 0) add(u, M[I[p]], P, S, Q, cnt, C, V);
                //for(auto it:M[I[p]]) cerr << it.first+1 << " " << it.second+1 << " ";
                //cerr << "\n";
                //for(auto it:cnt) cerr << it << " ";
                //cerr << "\n";
            }
        }
    }
    return true;
}

void solve(){
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> C(n), cnt(k);
    vector<vector<int>> W(k), G(n);
    vector<pair<int, int>> E;
    for(int i=0; i<n; i++){
        int a;
        cin >> a;
        a--;
        C[i] = a;
        cnt[a]++;
        W[a].push_back(i);
    }
    for(int i=0; i<m; i++){
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        E.push_back({u, v});
        G[u].push_back(v);
        G[v].push_back(u);
    }

    vector<int> S(n, 1);
    vector<int> P(n);
    for(int i=0; i<n; i++) P[i] = i;
    queue<int> Q;
    vector<bool> V(n);
    for(auto e:E){
        int u = e.first, v = e.second;
        if(C[u] == C[v] && f(u, P) != f(v, P)) onion(u, v, P, S, cnt, C, Q, V);
    }
    for(int i=0; i<k; i++)
        if(cnt[i] <= 1 && !V[i]){
            V[i] = true;
            Q.push(i);
        } 

    if(check(G, Q, W, C, P, S, cnt, V)) cout << "TAK\n";
    else cout << "NIE\n";
}
    

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    for(int i=0; i<t; i++){
        //cerr << i << "\n";
        solve();
    }
}