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
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
#include <iostream>
#include <vector>
#include <set>

int cases, n, m, k;
int const max_N = 200000;
using namespace std;
vector<int> vote;
vector<vector<int>> roads;
bool visited[max_N];

vector<int> comp_vote;
vector<vector<int>> conn_comp;
vector<set<pair<int, int>>> comp_edges;
int comp_count[max_N];
int city_comp[max_N];

int head_region[max_N];
int size_region[max_N];
int marked[max_N];
vector<int> single_components;

void DFS_conn(int u, bool initial) {
    if (!visited[u]) {
        visited[u] = true;
        if (initial) {
            conn_comp.push_back(vector<int>());
            comp_vote.push_back(vote[u]);
            comp_count[vote[u]]++;
        } 
        conn_comp.back().push_back(u);
        city_comp[u] = conn_comp.size() - 1;
        for (auto v : roads[u]) {
            if (vote[v] == vote[u]) {
                DFS_conn(v, false);
            }
        }
    }
}

void decrease_count(int comp) {
    int vote = comp_vote[comp];
    comp_count[vote]--;
    if (comp_count[vote] == 1) {
        single_components.push_back(comp);
    }
}

void create_comp_graph() {
    for (int comp = 0; comp < conn_comp.size(); comp++) {
        for (int u : conn_comp[comp]) {
            for (int v : roads[u]) {
                if (city_comp[v] != comp) {
                    comp_edges[comp].insert({vote[v], city_comp[v] });
                }
            }
        }
    }
}

int get_region_head(int comp) {
    while (comp != head_region[comp]) comp = head_region[comp];
    return comp;
}

bool same_region(int comp1, int comp2) {
    return get_region_head(comp1) == get_region_head(comp2);
}

//Connects and return the new head
int weak_merge(int comp1, int comp2) {
    int head1 = get_region_head(comp1);
    int head2 = get_region_head(comp2);

    if (size_region[head1] < size_region[head2]) 
        swap(head1, head2);
    size_region[head1] += size_region[head2];
    head_region[head2] = head_region[head1];
    //TODO: remove each other edges.
    if (comp_edges[head1].size() < comp_edges[head2].size())
        swap(comp_edges[head1], comp_edges[head2]);
    for (auto u : comp_edges[head2]) {
        comp_edges[head1].insert(u);
    }
    decrease_count(head1); //number of connected compotents of given party was reduced by 1.
    return head1;
}

void strong_merge(int comp1, int comp2) {
    int head1 = get_region_head(comp1);
    int head2 = get_region_head(comp2);

    if (size_region[head1] < size_region[head2])
        swap(head1, head2);
    size_region[head1] += size_region[head2];
    head_region[head2] = head_region[head1];
    if (comp_edges[head1].size() < comp_edges[head2].size())
        swap(comp_edges[head1], comp_edges[head2]);
    for (auto u : comp_edges[head2]) {
        auto it = comp_edges[head1].lower_bound({ u.first, -1 });
        if (it != comp_edges[head1].end()) { //not append if a repeat of a party, then also merge them into single region.
            int other_vote = (*it).first;
            int other_comp = (*it).second;
            int other_head = get_region_head(other_comp);
            if (!marked[other_head]) {
                if (other_head != get_region_head(u.second)) {
                    if (other_vote == u.first) {//found diferent component of the same party, but not yet marked
                        weak_merge(other_head, u.second);
                    }
                    else {
                        comp_edges[head1].insert(u);
                    }
                }
            }
            else {
                comp_edges[head1].insert(u);
            }
        }
        else {
            comp_edges[head1].insert(u);
        }
    }
}
void remove_duplicates(int head1) {
    set<pair<int, int>> tmp = set<pair<int, int>>();
    for (auto x : comp_edges[head1]) {
        if (!marked[x.second]) {
            auto it = tmp.lower_bound({ x.first, -1 });
            if (it != tmp.end() && (*it).first == x.first) { //already includes this party
                if (!same_region((*it).second, x.second)) {
                    weak_merge((*it).second, x.second);
                }
            }
            else {
                tmp.insert(x);
            }
        }
        else {
            tmp.insert(x); //leave connections to marked. They will be pruned later.
        }
    }
    swap(comp_edges[head1], tmp);
}


int main()
{
cin >> cases;
for (int cases_i = 0; cases_i < cases; cases_i++) {
    cin >> n >> m >> k;
    vote = vector<int>();
    roads = vector<vector<int>>();
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        a--;
        vote.push_back(a);
        roads.push_back(vector<int>());
        visited[i] = false;
    }
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        roads[a].push_back(b);
        roads[b].push_back(a);
    }
    //if (cases_i == 96) {
    //    cout << "\n\n\n\n\n\n";
    //}

    for (int i = 0; i < k; i++) {
        comp_count[i] = 0;
    }

    comp_vote = vector<int>();
    conn_comp = vector<vector<int>>();
    for (int i = 0; i < n; i++) {
        DFS_conn(i, true);
    }
    bool has_connected = false;
    comp_edges = vector<set<pair<int, int>>>();
    for (int i = 0; i < k; i++) {
        if (comp_count[i] == 1) {
            has_connected = true;
            break;
        }
    }
    if (!has_connected) {
        cout << "NIE\n";
        continue;
    }
    for (int i = 0; i < conn_comp.size(); i++) {
        comp_edges.push_back(set<pair<int, int>>());
        marked[i] = false;
        head_region[i] = i;
    }
    create_comp_graph();

    //ITERATE OVER CONNECTED PARTIES 
    bool found_new = false;
    bool first_iteration = true;
    bool impossible = false;
    single_components = vector<int>();
    for (int i = 0; i < conn_comp.size(); i++) {
        size_region[i] = 1;
        if (comp_count[comp_vote[i]] == 1) {
            single_components.push_back(i);
        }
    }
    set<int> to_check;
    int marked_count = 0;
    while (marked_count != conn_comp.size()) { //REPEAT UNTIL EVERYTHING IS ONE REGION
        found_new = single_components.size() > 0;
        to_check = set<int>();
        for (auto u : single_components) {
            int head = get_region_head(u);
            to_check.insert(head);
            marked_count += size_region[head];
        }
        single_components = vector<int>();
        if (!found_new) {
            impossible = true;
            cout << "NIE\n";
            break;
        }
        for (int i : to_check) {
            marked[i] = true;
        }
        for (int i : to_check) {
            remove_duplicates(i);
        }
        for (int i : to_check) {
            vector<pair<int, int>> tmp = vector<pair<int, int>>();
            for (auto u : comp_edges[get_region_head(i)]) { //NEED TO COPY AS I WILL MODIFY IT.
                tmp.push_back(u);
            }
            for (auto u : tmp) {
                //TODO: DO I HAVE TO CHECK IF NOT ALREADY PROCESSED? 
                //NO, because then they would be in the same region
                int head_u = get_region_head(u.second);
                if (marked[head_u]) {
                    int head_i = get_region_head(i);
                    comp_edges[head_i].erase(u); //TODO:
                    //comp_edges[get_region_head(u.second)].erase({ comp_vote[head_i], head_i });
                    if (head_u != head_i) {
                        strong_merge(head_u, head_i);
                    }
                }
            }
        }
        first_iteration = false;
    }
    if (!impossible) {
        cout << "TAK\n";
    }
}
}