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
#include <bits/stdc++.h>
using namespace std;
using ind = long long;
using cind = const ind;
#define FOR(i,l,r) for(ind i = (l); i <= (r); i++)
#define FORD(i,l,r) for(ind i = (l); i >= (r); i--)
#define DEBUG_ON false
#define debug if constexpr(DEBUG_ON)
#define err debug cerr

ind color[100'001];
ind my_group_id[100'001];
vector<ind> group_elements[100'001];
vector<ind> group_edges[100'001];
ind color_amount[100'001];
vector<ind> active_colors;

void merge(ind a, ind b){
    a = my_group_id[a];
    b = my_group_id[b];
    if(a==b) return;
    color_amount[color[a]]--;
    if(group_edges[b].size() + group_elements[b].size() > group_edges[a].size() + group_elements[a].size()) swap(a,b);
    for(auto k : group_edges[b]) group_edges[a].push_back(k);
    for(auto k : group_elements[b]) group_elements[a].push_back(k);
    for(auto k : group_elements[b]) my_group_id[k] = a;
    group_edges[b].clear();
    group_elements[b].clear();
    if(color_amount[color[a]]<=1) active_colors.push_back(a);
}
void solve(){
    ind N, M, K;
    cin >> N >> M >> K;
    FOR(i,1,N) group_edges[i].clear();
    FOR(i,1,N) cin >> color[i]; //color[i]=0;
    FOR(i,1,K) color_amount[i] = 0;
    FOR(i,1,N) color_amount[color[i]]++;
    FOR(i,1,N) my_group_id[i] = i;
    FOR(i,1,N) group_elements[i].resize(1);
    FOR(i,1,N) group_elements[i][0]=i;
    FOR(i,1,N) if(color_amount[color[i]]==1) active_colors.push_back(i);
    FOR(i,1,M){
        ind a,b;
        cin >> a >> b;
        if(color[a] == color[b]) merge(a,b);
        else{
            group_edges[my_group_id[a]].push_back(my_group_id[b]);
            group_edges[my_group_id[b]].push_back(my_group_id[a]);
        }
    }
    while(active_colors.size() > 0){
        ind vertex = my_group_id[active_colors.back()];
        active_colors.pop_back();
        map<ind,set<ind>> groups_to_connect;
        vector<ind> to_merge;
        for(auto e : group_edges[vertex]){
            if(my_group_id[e]==vertex) continue;
            ind e2 = my_group_id[e];
            if(color_amount[color[e2]] <= 1) to_merge.push_back(e2);
            else groups_to_connect[color[e2]].insert(e2);
        }
        for(auto m1 : groups_to_connect){
            ind s0=-1;
            for(auto s1 : m1.second){
                if(s0 == -1) {s0 = s1; continue;}
                merge(s0,s1);
            }
        }
        group_edges[vertex].clear();
        for(auto m1 : to_merge){
            merge(m1,vertex);
        }
        vertex = my_group_id[vertex];
        for(auto k : groups_to_connect){
            for(auto q : k.second){
                group_edges[vertex].push_back(q);
                break;
            }
        }
    }
    FOR(i,1,K) if(color_amount[i] > 1) {cout << "NIE\n"; return;}
    cout << "TAK\n";
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ind T;
    cin >> T;
    FOR(i,1,T) solve();
}