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
#include<set>
#include<vector>
#include<queue>
#include <cstdio>

template<class T>
struct ZbioryRozlaczne {
	struct Element {
		T reprezentant = T(-1);
		T stopien = T(0);
	};

    std::vector<Element> elementy;

	ZbioryRozlaczne(){}

	ZbioryRozlaczne(T elementow):elementy(elementow, Element()){}

	T dodajElement(){
		elementy.push_back(Element());
		return T(elementy.size()-1);
	}

	T reprezentant(T a) {
		T rodzic = elementy[a].reprezentant;
		if (rodzic == -1) {
			return a;
		}
		return (elementy[a].reprezentant = reprezentant(rodzic));
	}

	void zlacz(T a, T b) {
		T reprA = reprezentant(a);
		T reprB = reprezentant(b);
		T stopienRA = elementy[reprA].stopien;
		T stopienRB = elementy[reprB].stopien;
		if (stopienRB < stopienRA) {
			elementy[reprB].reprezentant = reprA;
		} else if (stopienRA < stopienRB) {
			elementy[reprA].reprezentant = reprB;
		} else if (reprA != reprB) {
			elementy[reprB].reprezentant = reprA;
			++elementy[reprA].stopien;
		}
	}
};

int main() {
	int wojewodztw;
	scanf("%d", &wojewodztw);

    while (wojewodztw-->0) {
        int miast;
        int drog;
        size_t partyj;
        scanf("%d %d %lu", &miast, &drog, &partyj);
        std::vector<int> zwyciezca;
        std::vector<std::set<int>> sasiedzi_miasta(miast);
        //std::vector<std::set<int>> sasiedzi_skladowej(miast);
        ZbioryRozlaczne skladowe(miast);
        std::vector<int> skladowych(partyj+1, 0);
        std::vector<size_t> miast_wg_zwyciezcy(partyj, 0);
        zwyciezca.reserve(miast);
        for (int i=0; i<miast; ++i) {
            int z;
            scanf("%d", &z);
            zwyciezca.emplace_back(z);
            skladowych[z] += 1;
            miast_wg_zwyciezcy[z] += 1;
        }
        for (int i=0; i<drog; ++i) {
            int z, ku;
            scanf("%d %d", &z, &ku);
            --z;
            --ku;
            if (zwyciezca[z] != zwyciezca[ku]) {
                sasiedzi_miasta[z].insert(ku);
                sasiedzi_miasta[ku].insert(z);
            } else if (zwyciezca[z] == zwyciezca[ku] && skladowe.reprezentant(z) != skladowe.reprezentant(ku)) {
                // int rep_z = skladowe.reprezentant(z);
                // int rep_ku = skladowe.reprezentant(ku);
                skladowe.zlacz(z, ku);
                /*
                //if (rep_z != skladowe.reprezentant(z)) {
                    //sasiedzi_skladowej[skladowe.reprezentant(z)].insert(sasiedzi_skladowej(rep_z).begin(), sasiedzi_skladowej[rep_z].end());
                //}
                // przepnij krawędzie
                */
                skladowych[zwyciezca[z]] -= 1;
            }
        }
        std::set<int> spojne;
        std::queue<int> do_sprawdzenia;
        auto przejazd_do_skladowych = [&](int wierzcholek){
            std::queue<int> wierzcholki;
            wierzcholki.push(wierzcholek);
            std::set<int> osiagalne_wlasne;
            std::set<int> osiagalne_niczyje;
            while (!wierzcholki.empty()) {
                int a = wierzcholki.front();
                wierzcholki.pop();
                for (int sasiad: sasiedzi_miasta[a]) {
                    if (zwyciezca[sasiad] == zwyciezca[wierzcholek]) {
                        if (osiagalne_wlasne.find(sasiad) == osiagalne_wlasne.end()){
                            osiagalne_wlasne.insert(sasiad);
                            wierzcholki.push(sasiad);
                        }
                    }
                    else if (spojne.find(zwyciezca[sasiad]) != spojne.end()) {
                        if (osiagalne_niczyje.find(sasiad) == osiagalne_niczyje.end()){
                            osiagalne_niczyje.insert(sasiad);
                            wierzcholki.push(sasiad);
                        }
                    }
                }
            }
            return (osiagalne_wlasne.size() == miast_wg_zwyciezcy[zwyciezca[wierzcholek]]);
        };
        for (int i=0; i<miast; ++i) {
            if (skladowych[zwyciezca[i]] == 1) {
                spojne.insert(zwyciezca[i]);
                for (int s: sasiedzi_miasta[i]) {
                    do_sprawdzenia.push(s);
                }
            }
        }
        for (int i=0; i<partyj; ++i) {
            if (skladowych[i] == 0) {
                spojne.insert(i);
            }
        }
        while (!do_sprawdzenia.empty()) {
            int a = do_sprawdzenia.front();
            fprintf(stderr, "sprawdzam %d \n", a);
            do_sprawdzenia.pop();
            if (spojne.find(zwyciezca[a]) != spojne.end()) {
                continue;
            }
            if (przejazd_do_skladowych(a)) {
                spojne.insert(zwyciezca[a]);
                for (int s: sasiedzi_miasta[a]) {
                    do_sprawdzenia.push(s);
                }
            }
        }
        for(int i: spojne) {
            fprintf(stderr, "%d ", i);
        }
        if (spojne.size() == partyj) {
            printf("TAK");
        } else {
            printf("NIE");
        }
    }
}