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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

queue <int> q;

int Find(int x, vector<int> &parent) {
    if (x != parent[x]) parent[x] = Find(parent[x], parent);
    return parent[x];
}

void UnionPartie(int a, int b, int c, vector<int> &ileRoznychSkladowych, vector<int> &parentPart, vector<bool> &uzyty, vector<bool> &wKolejce) {
    a = Find(a, parentPart);
    b = Find(b, parentPart);
    if (a == b) return;
    parentPart[b] = a;
    ileRoznychSkladowych[c]--;
    if (ileRoznychSkladowych[c] == 1 && !uzyty[c] && !wKolejce[c]) {
        q.push(c);
        wKolejce[c] = true;
    }
}

int UnionZrobione(int a, int b, vector<int> &parentZrobione, vector<unordered_map<int,int>> &repr,vector<int> &rozmZrobione, vector<int> &parentPart, vector<int> &ileRoznychSkladowych, vector<bool> &uzyty, vector<bool> &wKolejce) {
    a = Find(a, parentZrobione);
    b = Find(b, parentZrobione);
    if (a == b) return a;
    if (repr[a].size() < repr[b].size()) swap(a, b);
    parentZrobione[b] = a;
    rozmZrobione[a] += rozmZrobione[b];
    for (auto &[c,przedst] : repr[b]) {
        auto tym = repr[a].find(c);
        if (tym == repr[a].end()) {
            repr[a][c] = przedst;
        } else {
            UnionPartie(tym->second, przedst,c,ileRoznychSkladowych, parentPart, uzyty, wKolejce);
        }
    }
    repr[b].clear();
    return a;
}

int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n, m, k;
        cin >> n >> m >> k;
        vector<int> miasta(n);
        for (int i = 0; i < n; i++) {
            cin >> miasta[i];
            miasta[i]--;
        }
        vector<vector<int>> graf(n);
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            a--,b--;
            graf[a].push_back(b);
            graf[b].push_back(a);
        }
        vector<int> wKtorejSkladowej(n), kolorSkladowej;
        vector<vector<int>> wKolorze(k);
        int nrSkladowej = 0;
        vector <bool> odwiedzony(n,false);
        for (int i = 0; i < n; i++) {
            if (odwiedzony[i]) continue;
            q.push(i);
            while (!q.empty()) {
                int v = q.front();
                q.pop();
                odwiedzony[v] = true;
                wKtorejSkladowej[v] = nrSkladowej;
                for (auto u : graf[v]) {
                    if (odwiedzony[u]) continue;
                    if (miasta[v] == miasta[u]) {
                        odwiedzony[u] = true;
                        q.push(u);
                    }
                }
            }
            kolorSkladowej.push_back(miasta[i]);
            wKolorze[miasta[i]].push_back(nrSkladowej);
            nrSkladowej++;
        }

        vector<vector<int>> grafSkladowych(nrSkladowej);
        for (int i = 0; i < n; i++) {
            for (auto j : graf[i]) {
                int v = wKtorejSkladowej[i], u = wKtorejSkladowej[j];
                if (u != v) grafSkladowych[v].push_back(u);
            }
        }
        vector<int> parentPart(nrSkladowej), rozmPart(nrSkladowej,1);
        vector<int> ileRoznychSkladowych(k);
        vector<int> parentZrobione(nrSkladowej), rozmZrobione(nrSkladowej,1);
        for (int i = 0; i < nrSkladowej; i++) {
            parentPart[i] = i;
            parentZrobione[i] = i;
        }
        for (int i = 0; i < k; i++) ileRoznychSkladowych[i] = wKolorze[i].size();
        vector<unordered_map<int,int>> repr(nrSkladowej);
        vector<bool> zrobione(nrSkladowej,false), uzyty(k,false), wKolejce(k,false);
        for (int i=0; i < k; i++) {
            if(ileRoznychSkladowych[i]<=1){
                q.push(i); 
                wKolejce[i]=true;
            }
        }

        while(!q.empty()){
            int v = q.front(); 
            q.pop(); 
            wKolejce[v]=false;
            if(uzyty[v] || ileRoznychSkladowych[v]>1) continue;
            uzyty[v]=true;
            if(wKolorze[v].empty()) continue;
            for(int u : wKolorze[v]){
                zrobione[u]=true;
                rozmZrobione[u]=1;
                repr[u].clear();
                repr[u][v]=u;
            }

            for(int u : wKolorze[v]){
                int przedst = Find(u,parentZrobione);
                for(int z : grafSkladowych[u]){
                    if(zrobione[z]){
                        przedst = UnionZrobione(przedst,z,parentZrobione,repr,rozmZrobione,parentPart,ileRoznychSkladowych,uzyty,wKolejce);
                    } else {
                        int nu = kolorSkladowej[z];
                        auto &curr = repr[przedst];
                        auto tym = curr.find(nu);
                        if(tym==curr.end()) curr[nu]=z;
                        else UnionPartie(tym->second,z, nu,ileRoznychSkladowych,parentPart,uzyty,wKolejce);
                    }
                }
            }
        }
        bool daSie = true;
        for (int i = 0; i < k; i++) {
            if (!uzyty[i]) {
                daSie = false;
                break;
            }
        }
        if (daSie) cout << "TAK\n";
        else cout << "NIE\n";
    }
    return 0;
}