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

const int MAXN = 100005;

int sel_par[MAXN];
int sel_sz[MAXN];
int pc_par[MAXN];

int find_sel(int x) {
    while (sel_par[x] != x) { sel_par[x] = sel_par[sel_par[x]]; x = sel_par[x]; }
    return x;
}

int find_pc(int x) {
    while (pc_par[x] != x) { pc_par[x] = pc_par[pc_par[x]]; x = pc_par[x]; }
    return x;
}

unordered_map<int,int> cmap[MAXN];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t; cin >> t;
    while (t--) {
        int n, m, k; 
        cin >> n >> m >> k;

        vector<int> a(n+1);
        for (int i = 1; i <= n; i++) cin >> a[i];

        vector<pair<int,int>> edges(m);
        for (int i = 0; i < m; i++) cin >> edges[i].first >> edges[i].second;

        for (int i = 1; i <= n; i++) {
            sel_par[i] = i; sel_sz[i] = 1;
            pc_par[i] = i;
            cmap[i].clear();
        }

        vector<vector<int>> adj(n+1), W(k+1);
        vector<int> W_sz(k+1, 0), cnt(k+1, 0);
        vector<bool> is_sel(n+1, false), party_done(k+1, false);

        for (int i = 1; i <= n; i++) { W_sz[a[i]]++; W[a[i]].push_back(i); }
        for (auto& [u,v] : edges) { adj[u].push_back(v); adj[v].push_back(u); }

        for (int p = 1; p <= k; p++) cnt[p] = W_sz[p];
        for (auto& [u,v] : edges) {
            if (a[u] == a[v]) {
                int pu = find_pc(u), pv = find_pc(v);
                if (pu != pv) { pc_par[pv] = pu; cnt[a[u]]--; }
            }
        }

        queue<int> Q;
        int nonempty = 0;
        for (int p = 1; p <= k; p++) {
            if (W_sz[p] > 0) { nonempty++; if (cnt[p] == 1) Q.push(p); }
        }

        auto touch_sel = [&](int C, int q, int v) {
            int pv = find_pc(v);
            auto it = cmap[C].find(q);
            if (it == cmap[C].end()) {
                cmap[C][q] = pv;
            } else {
                int rep = find_pc(it->second);
                if (rep != pv) {
                    pc_par[pv] = rep;
                    cnt[q]--;
                    it->second = rep;
                    if (W_sz[q] > 0 && !party_done[q] && cnt[q] == 1) Q.push(q);
                }
            }
        };

        auto unite_sel = [&](int u, int v) {
            int A = find_sel(u), B = find_sel(v);
            if (A == B) return;

            if (sel_sz[A] < sel_sz[B]) swap(A, B);
            if (cmap[A].size() < cmap[B].size()) swap(cmap[A], cmap[B]);

            for (auto& [q, rep_b] : cmap[B]) {
                int rb = find_pc(rep_b);
                auto it = cmap[A].find(q);
                if (it == cmap[A].end()) {
                    cmap[A][q] = rb;
                } else {
                    int ra = find_pc(it->second);
                    if (ra != rb) {
                        pc_par[rb] = ra;
                        cnt[q]--;
                        it->second = ra;
                        if (W_sz[q] > 0 && !party_done[q] && cnt[q] == 1) Q.push(q);
                    }
                }
            }
            cmap[B].clear();
            sel_par[B] = A;
            sel_sz[A] += sel_sz[B];
        };

        int done = 0;
        while (!Q.empty()) {
            int p = Q.front(); Q.pop();
            if (party_done[p]) continue;
            party_done[p] = true; done++;

            for (int u : W[p]) is_sel[u] = true;

            for (int u : W[p]) {
                for (int v : adj[u]) {
                    if (is_sel[v]) {
                        unite_sel(u, v);
                    } else if (!party_done[a[v]]) {
                        touch_sel(find_sel(u), a[v], v);
                    }
                }
            }
        }

        cout << (done == nonempty ? "TAK" : "NIE") << "\n";
    }
}