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
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <numeric>
#include <utility>
#include <algorithm>
using namespace std;

struct DSU {
    vector<int> parent, sz;
    DSU() {}
    DSU(int n) : parent(n), sz(n, 1) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
    pair<int,int> unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return {-1,-1};
        if (sz[x] < sz[y]) swap(x,y);
        parent[y] = x; sz[x] += sz[y];
        return {x, y};
    }
};

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

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

    vector<vector<int>> adj(n+1);
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<vector<int>> party_cities(k+1);
    for (int i = 1; i <= n; i++) party_cities[a[i]].push_back(i);

    DSU q_dsu(n+1);
    for (int u = 1; u <= n; u++)
        for (int v : adj[u])
            if (a[u] == a[v] && u < v)
                q_dsu.unite(u, v);

    vector<int> comp_cnt(k+1, 0);
    for (int i = 1; i <= n; i++)
        if (q_dsu.find(i) == i)
            comp_cnt[a[i]]++;

    DSU avail_dsu(n+1);
    vector<bool> available(n+1, false);

    vector<unordered_map<int,int>> adj_data(n+1);
    vector<int> avail_rep(n+1);
    iota(avail_rep.begin(), avail_rep.end(), 0);

    vector<bool> peeled(k+1, false);
    vector<bool> in_queue(k+1, false);
    queue<int> Q;

    for (int p = 1; p <= k; p++)
        if (comp_cnt[p] == 1) { Q.push(p); in_queue[p] = true; }

    auto add_adj = [&](int slot_A, int q, int qr) {
        qr = q_dsu.find(qr);
        auto it = adj_data[slot_A].find(q);
        if (it == adj_data[slot_A].end()) {
            adj_data[slot_A][q] = qr;
        } else {
            int existing = q_dsu.find(it->second);
            if (existing != qr) {
                auto [nr, _] = q_dsu.unite(existing, qr);
                comp_cnt[q]--;
                if (comp_cnt[q] == 1 && !peeled[q] && !in_queue[q]) {
                    Q.push(q); in_queue[q] = true;
                }
                it->second = nr;
            }
        }
    };

    auto merge_avail = [&](int u, int v) {
        auto [new_root, old_root] = avail_dsu.unite(u, v);
        if (new_root == -1) return;

        int A = avail_rep[new_root], B = avail_rep[old_root];
        if (adj_data[A].size() < adj_data[B].size()) swap(A, B);
        avail_rep[new_root] = A;

        for (auto& [q, qr] : adj_data[B])
            add_adj(A, q, qr);
        adj_data[B].clear();
    };

    while (!Q.empty()) {
        int p = Q.front(); Q.pop();
        if (peeled[p]) continue;
        peeled[p] = true;

        for (int u : party_cities[p]) available[u] = true;

        for (int u : party_cities[p])
            for (int v : adj[u])
                if (available[v])
                    merge_avail(u, v);

        for (int u : party_cities[p])
            for (int v : adj[u])
                if (!available[v])
                    add_adj(avail_rep[avail_dsu.find(u)], a[v], q_dsu.find(v));
    }

    for (int p = 1; p <= k; p++)
        if (!party_cities[p].empty() && !peeled[p]) {
            cout << "NIE\n"; return;
        }
    cout << "TAK\n";
}

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