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

struct DSU {
    vector<int>rep, sz;

    DSU(int n){
        rep.resize(n+1);
        iota(rep.begin(), rep.end(), 0);
        sz.assign(n+1, 1);
    }

    int f(int a){
        return a == rep[a] ? a : rep[a] = f(rep[a]);
    }

    T u(int a, int b){
        a = f(a);
        b = f(b);
        if (a == b) return {-1, -1};
        if (sz[a] < sz[b]) swap(a, b);
        sz[a] += sz[b];
        rep[b] = a;
        return {a, b};
    }
};

void solve() {
    int n, m, k; cin >> n >> m >> k;
    vector<vector<int>>g(n + 1), where(k + 1);
    vector<int>A(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
        where[A[i]].emplace_back(i);
    }
    
    vector<bool>vis(k + 1);
    queue<int>q;
    DSU colors(n + 1);    
    for (int i = 0; i < m; i++){
        int x, y; cin >> x >> y;
        g[x].emplace_back(y);
        g[y].emplace_back(x);
        if (A[x] == A[y]) {
            // cerr << "laczymy wierzcholki " << x << " " << y << endl;
            colors.u(x, y);
        }
    }
    DSU odw(k + 1);
    
    for (int i = 1; i <= k; i++) {
        if (where[i].empty()) continue;
        if (colors.sz[colors.f(where[i][0])] == (int)where[i].size()) {
            q.push(i);
        }
    }
    vector<unordered_map<int, int>>ile(k + 1);
    int vis_vert = 0;
    auto polacz = [&](int v, int v2, int col){
        // cerr << "laczymy wierzcholki " << v << " " << v2 << endl;
        if (colors.u(v, v2).first != -1) {
            if (colors.sz[colors.f(v)] == (int)where[col].size() && !vis[col]) {
                q.push(col);
            }
        }
    };
    while ((int)q.size()) {
        int c = q.front(); q.pop();
        vis[c] = 1;
        // cerr << c << endl;
        for (auto v: where[c]) {
            vis_vert++;
            for (auto x: g[v]){
                int nc = A[x];
                if (nc == c) continue;
                if (vis[nc]) {
                    // cerr << "laczymy kolory " << nc << " " << c << endl;
                    auto [a, b] = odw.u(nc, c);
                    if (a == -1) continue;
                    // cerr << "rep " << a << " " << b << endl;
                    for (auto [col, u]: ile[b]) {
                        if (ile[a].count(col)) {
                            int u2 = ile[a][col];
                            polacz(u, u2, col);
                        } else {
                            ile[a][col] = u;
                        }
                    }
                    ile[b].clear();
                } else {
                    // cerr << "wierzcholek " << x << "\n";
                    int rep = odw.f(c);
                    if (ile[rep].count(nc)) {
                        int u = ile[rep][nc];
                        polacz(u, x, nc);
                    } else {
                        ile[rep][nc] = x;
                    }
                }
            }
        }

    }
    cout << (vis_vert == n ? "TAK" : "NIE") << '\n';
}

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

    int t; cin >> t;
    for (int i = 1; i <= t; i++){
        solve();
    }

    return 0;
}