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

int find(vector<int> &p, int x1)
{
    if (p[x1] == x1)
        return x1;
    return p[x1] = find(p, p[x1]);
}

void join(vector<int> &p, int r1, int r2)
{
    if (r1 == r2)
        return;
    p[r2] = r1;
}

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

    int t;
    cin >> t;

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

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

        vector<vector<pair<int, int>>> g(n + 1);

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

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

        vector<int> licznik(k + 1, 0);
        for (int i=1; i<=n; i++)
            licznik[c[i]]++;

        vector<bool> vis(m + 1, false);

        vector<int> poczatek(n + 1), koniec(n + 1), nastepny(n + 1, 0);
        for(int i=1; i<=n; i++)
            poczatek[i] = koniec[i] = i;

        for (int u=1; u<=n; u++)
            for (auto [v, id] : g[u])
                if (u < v && c[u] == c[v]){
                    int r1 = find(p, u);
                    int r2 = find(p, v);
                    if (r1 != r2) {
                        join(p, r1, r2);
                        nastepny[koniec[r1]] = poczatek[r2];
                        koniec[r1] = koniec[r2];
                        licznik[c[u]]--;
                    }
                    vis[id] = true;
                }

        vector<int> rep(k + 1, 0);
        for (int i = 1; i <= n; i++)
            rep[c[i]] = find(p, i);

        queue<int> q;
        for (int c1 = 1; c1 <= k; c1++)
            if (licznik[c1] == 1)
                q.push(c1);

        int wynik = 0;
        vector<int> pierw(k + 1, 0);
        vector<int> laczone;

        while (!q.empty()){
            int col = q.front(); q.pop();
            int rep0 = find(p, rep[col]);

            int node = poczatek[rep0];
            while(node != 0){
                wynik++;
                for (auto [sasiad, id] : g[node])
                    if (!vis[id]){
                        vis[id] = true;

                        int rs = find(p, sasiad);
                        int cs = c[rs];

                        if (pierw[cs] == 0){
                            pierw[cs] = rs;
                            laczone.push_back(cs);
                        } else{
                            int r1 = find(p, pierw[cs]);
                            int r2 = rs;
                            if (r1 != r2) {
                                join(p, r1, r2);
                                        ///// laczenie linked list ********
                                nastepny[koniec[r1]] = poczatek[r2];
                                koniec[r1] = koniec[r2];


                                licznik[cs]--;
                                rep[cs] = r1;
                                pierw[cs] = r1;

                                if (licznik[cs] == 1)
                                    q.push(cs);
                            }
                        }
                    }
                node = nastepny[node];
            }

            for (int c1 : laczone)
                pierw[c1] = 0;
            laczone.clear();
        }

        if(wynik == n)
            cout <<  "TAK\n";
        else
            cout << "NIE\n";
    }
}