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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <cassert>


struct Miasto
{
    bool czyIstnieje = true;
    bool czyLaczace = false;
    int numerPartii = -1;
    std::unordered_set<int> sasiedzi;
    std::unordered_map<int, std::unordered_set<int>> partiaToSasiad;
};

struct Wojewodztwo
{

    std::vector<Miasto> miasta;
    std::vector<int> iloscMiastGlossujacychNaPartie;
    std::set<std::pair<int, int>> krawedzieDoPrzetworzenia;
    Wojewodztwo(int n, int k)
    {
        miasta.resize(n);
        iloscMiastGlossujacychNaPartie.resize(k + 1, 0);
    }
    void dodajKrawedz(int miasto1, int miasto2)
    {
        if (miasto1 == miasto2)
            return;
        if (miasta[miasto1].sasiedzi.count(miasto2) > 0)
            return;
        if (miasta[miasto2].sasiedzi.count(miasto1) > 0)
            return;
        miasta[miasto1].sasiedzi.insert(miasto2);
        miasta[miasto2].sasiedzi.insert(miasto1);
        miasta[miasto1].partiaToSasiad[miasta[miasto2].numerPartii].insert(miasto2);
        miasta[miasto2].partiaToSasiad[miasta[miasto1].numerPartii].insert(miasto1);
        krawedzieDoPrzetworzenia.insert(std::make_pair(miasto1, miasto2));
    }
    void usunKrawedz(int miasto1, int miasto2)
    {
        miasta[miasto1].sasiedzi.erase(miasto2);
        miasta[miasto2].sasiedzi.erase(miasto1);
        miasta[miasto1].partiaToSasiad[miasta[miasto2].numerPartii].erase(miasto2);
        miasta[miasto2].partiaToSasiad[miasta[miasto1].numerPartii].erase(miasto1);
    }
};

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

    int t;
    std::cin >> t;
    for (int test = 0; test < t; ++test)
    {
        int n;
        int m;
        int k;
        std::cin >> n >> m >> k;
        Wojewodztwo woj(n, k);
        for (int i = 0; i < n; ++i)
        {
            int numerPartii;
            std::cin >> numerPartii;
            woj.iloscMiastGlossujacychNaPartie[numerPartii]++;
            woj.miasta[i].numerPartii = numerPartii;
        }
        for (int i = 0; i < m; ++i)
        {
            int miasto1;
            int miasto2;
            std::cin >> miasto1 >> miasto2;
            woj.dodajKrawedz(miasto1 - 1, miasto2 - 1);
        }
        //if (test != 69)
        //    continue;
        for (int i = 0; i < n; ++i)
        {
            if (woj.iloscMiastGlossujacychNaPartie[woj.miasta[i].numerPartii] == 1)
            {
                woj.iloscMiastGlossujacychNaPartie[woj.miasta[i].numerPartii] = 0;
                woj.miasta[i].numerPartii = -1;
                woj.miasta[i].czyLaczace = true;
                for (int sasiad : woj.miasta[i].sasiedzi)
                {
                    woj.krawedzieDoPrzetworzenia.insert(std::make_pair(i, sasiad));
                }
                for (auto& tempSasiedziZTejSamejPartii : woj.miasta[i].partiaToSasiad)
                {
                    std::vector<int> sasiedziZTejSamejPartii(tempSasiedziZTejSamejPartii.second.begin(), tempSasiedziZTejSamejPartii.second.end());
                    for (int i = 1; i < sasiedziZTejSamejPartii.size(); ++i)
                    {
                        woj.dodajKrawedz(sasiedziZTejSamejPartii[0], sasiedziZTejSamejPartii[i]);
                    }
                }

            }

        }
        while (woj.krawedzieDoPrzetworzenia.size() > 0)
        {
            std::pair<int, int> analizowanaKrawedz = *woj.krawedzieDoPrzetworzenia.begin();
            woj.krawedzieDoPrzetworzenia.erase(woj.krawedzieDoPrzetworzenia.begin());
            int miasto1 = analizowanaKrawedz.first;
            int miasto2 = analizowanaKrawedz.second;
            if (!woj.miasta[miasto1].czyIstnieje)
                continue;
            if (!woj.miasta[miasto2].czyIstnieje)
                continue;
            int wiekszeMiasto = miasto1;
            int mniejszeMiasto = miasto2;
            if (woj.miasta[miasto1].sasiedzi.size() < woj.miasta[miasto2].sasiedzi.size())
            {
                wiekszeMiasto = miasto2;
                mniejszeMiasto = miasto1;
            }

            if (!woj.miasta[wiekszeMiasto].czyLaczace && !woj.miasta[mniejszeMiasto].czyLaczace && woj.miasta[wiekszeMiasto].numerPartii == woj.miasta[mniejszeMiasto].numerPartii)
            {
                //std::cerr << "Merging: " << wiekszeMiasto << " " << mniejszeMiasto << "\n";
                /*if (wiekszeMiasto == 1 && mniejszeMiasto == 2)
                {
                    std::cerr << "AA";
                }*/
                woj.usunKrawedz(wiekszeMiasto, mniejszeMiasto);
                std::unordered_set<int> sasiedzi = woj.miasta[mniejszeMiasto].sasiedzi;
                for (int sasiad : sasiedzi)
                {
                    woj.dodajKrawedz(wiekszeMiasto, sasiad);
                    woj.usunKrawedz(mniejszeMiasto, sasiad);
                }
                woj.miasta[mniejszeMiasto].sasiedzi.clear();
                woj.miasta[mniejszeMiasto].numerPartii = -1;
                woj.miasta[mniejszeMiasto].czyIstnieje = false;
                woj.iloscMiastGlossujacychNaPartie[woj.miasta[wiekszeMiasto].numerPartii]--;
                if (woj.iloscMiastGlossujacychNaPartie[woj.miasta[wiekszeMiasto].numerPartii] == 1)
                {
                    for (int sasiad : woj.miasta[wiekszeMiasto].sasiedzi)
                    {
                        woj.krawedzieDoPrzetworzenia.insert(std::make_pair(wiekszeMiasto, sasiad));
                    }

                    for (auto& tempSasiedziZTejSamejPartii : woj.miasta[wiekszeMiasto].partiaToSasiad)
                    {

                        std::vector<int> sasiedziZTejSamejPartii(tempSasiedziZTejSamejPartii.second.begin(), tempSasiedziZTejSamejPartii.second.end());
                        for (int i = 1; i < sasiedziZTejSamejPartii.size(); ++i)
                            woj.dodajKrawedz(sasiedziZTejSamejPartii[0], sasiedziZTejSamejPartii[i]);
                    }

                    woj.iloscMiastGlossujacychNaPartie[woj.miasta[wiekszeMiasto].numerPartii] = 0;
                    woj.miasta[wiekszeMiasto].numerPartii = -1;
                    woj.miasta[wiekszeMiasto].czyLaczace = true;
                }
            }
            if (woj.miasta[wiekszeMiasto].czyLaczace && woj.miasta[mniejszeMiasto].czyLaczace)
            {
                /*std::cerr << "Merging laczace: " << wiekszeMiasto << " " << mniejszeMiasto << "\n";
                if (wiekszeMiasto == 0 && mniejszeMiasto == 5)
                {
                    std::cerr << "AA";
                }*/
                std::unordered_set<int> sasiedzi = woj.miasta[mniejszeMiasto].sasiedzi;
                for (int sasiad : sasiedzi)
                {
                    //if (woj.miasta[sasiad].czyLaczace)
                    //    continue;
                    if (!woj.miasta[sasiad].czyLaczace && woj.miasta[wiekszeMiasto].partiaToSasiad.count(woj.miasta[sasiad].numerPartii))
                    {
                        
                        woj.dodajKrawedz((*woj.miasta[wiekszeMiasto].partiaToSasiad[woj.miasta[sasiad].numerPartii].begin()), sasiad);
                    }
                    /*for (auto& tempSasiedziZTejSamejPartii : woj.miasta[wiekszeMiasto].partiaToSasiad)
                    {
                        auto sasiedziZTejSamejPartii = tempSasiedziZTejSamejPartii;
                        for (int i = 1; i < sasiedziZTejSamejPartii.second.size(); ++i)
                            woj.dodajKrawedz(sasiedziZTejSamejPartii.second[0], sasiedziZTejSamejPartii.second[i]);
                    }*/
                    woj.dodajKrawedz(wiekszeMiasto, sasiad);
                    woj.usunKrawedz(mniejszeMiasto, sasiad);
                }
                woj.usunKrawedz(wiekszeMiasto, mniejszeMiasto);
                woj.miasta[mniejszeMiasto].sasiedzi.clear();
                woj.miasta[mniejszeMiasto].numerPartii = -1;
                woj.miasta[mniejszeMiasto].czyIstnieje = false;

            }
        }
        bool czySukces = true;
        for (int i = 0; i < woj.iloscMiastGlossujacychNaPartie.size(); ++i)
        {
            if (woj.iloscMiastGlossujacychNaPartie[i] > 0)
                czySukces = false;
        }
        if (czySukces)
            std::cout << "TAK\n";
        else
            std::cout << "NIE\n";
    }

    return 0;
}