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 <bits/stdc++.h>
#define ll long long
using namespace std;

int find(int x, unordered_map<int, int>& parents){ return parents[x] == x ? x : (parents[x] = find(parents[x], parents));}

bool unite(int x, int y, unordered_map<int, int>& parents, unordered_map<int, int>& sizes){
	int x_root = find(x, parents);
	int y_root = find(y, parents);
	if (x_root == y_root) return false;

	if (sizes[x_root] < sizes[y_root]) swap(x_root, y_root);
	sizes[x_root] += sizes[y_root];
	parents[y_root] = x_root;
	return true;
}
 
int dead_find(int x, vector<int>& dead_parents){ return dead_parents[x] == x ? x : (dead_parents[x] = dead_find(dead_parents[x], dead_parents));}

void add_touch(int dead_root, int c, int v, vector<int>& dead_parents, vector<unordered_map<int, int>>& dead_touch, vector<bool>& done, vector<unordered_map<int, int>>& dsu_parents, vector<unordered_map<int, int>>& dsu_sizes, vector<int>& scc_counter, vector<int>& to_do){
    if(done[c]) return;
    dead_root = dead_find(dead_root, dead_parents);

    if(!dead_touch[dead_root].count(c)) dead_touch[dead_root][c] = v;
    else{
        if(unite(v, dead_touch[dead_root][c], dsu_parents[c], dsu_sizes[c])){
            scc_counter[c]--;
            if(scc_counter[c] == 1) to_do.push_back(c);
        }
    }
}

int dead_unite(int x, int y, vector<int>& dead_parents, vector<int>& dead_sizes, vector<unordered_map<int, int>>& dead_touch, vector<bool>& done, vector<unordered_map<int, int>>& dsu_parents, vector<unordered_map<int, int>>& dsu_sizes, vector<int>& scc_counter, vector<int>& to_do){
    x = dead_find(x, dead_parents);
    y = dead_find(y, dead_parents);
    if(x == y) return x;

    if(dead_sizes[x] < dead_sizes[y]) swap(x, y);
    dead_sizes[x] += dead_sizes[y];
    dead_parents[y] = x;

    if(dead_touch[x].size() < dead_touch[y].size()) swap(dead_touch[x], dead_touch[y]);

    for(auto [c, v]: dead_touch[y]){
        if(done[c]) continue;

        if(!dead_touch[x].count(c)) dead_touch[x][c] = v;
        else{
            if(unite(v, dead_touch[x][c], dsu_parents[c], dsu_sizes[c])){
                scc_counter[c]--;
                if(scc_counter[c] == 1) to_do.push_back(c);
            }
        }
    }

    dead_touch[y].clear();
    return x;
}

void solve(){
    int n, m, k; cin>>n>>m>>k;
    vector<int> colour(n+1, 0); for(int i=1; i<=n; i++) cin>>colour[i];
    vector<vector<int>> colourGroup(k+1); for(int i=1; i<=n; i++) colourGroup[colour[i]].push_back(i);
    vector<vector<pair<int, int>>> graph(n+1);

    for(int i=0; i<m; i++){
        int u, v; cin>>u>>v;
        graph[u].push_back({colour[v], v});
        graph[v].push_back({colour[u], u});
    }

    for(int i=0; i<=n; i++) sort(graph[i].begin(), graph[i].end());

    //-----------------------------
    vector<unordered_map<int, int>> dsu_parents(k+1);
    vector<unordered_map<int, int>> dsu_sizes(k+1);
    vector<int> scc_counter(k+1, 0);
    vector<int> to_do;
    vector<bool> done(k+1, 0);

    for(int i=1; i<=n; i++){
        dsu_parents[colour[i]][i] = i;
        dsu_sizes[colour[i]][i] = 1;
        scc_counter[colour[i]]++;
    }

    for(int i=1; i<=k; i++) if(scc_counter[i] == 0) done[i] = 1;

    for(int i=1; i<=n; i++){
        auto it_left = lower_bound(graph[i].begin(), graph[i].end(), make_pair(colour[i], 0));
        auto it_right = lower_bound(graph[i].begin(), graph[i].end(), make_pair(colour[i]+1, 0));

        while(it_left != it_right){
            if(unite(i, it_left->second, dsu_parents[colour[i]], dsu_sizes[colour[i]])) scc_counter[colour[i]]--;
            it_left++;
        }
    }

    for(int i=1; i<=k; i++) if(!done[i] && scc_counter[i] == 1) to_do.push_back(i);

    //-----------------------------
    vector<int> dead_parents(n+1), dead_sizes(n+1, 1);
    vector<bool> dead_active(n+1, 0);
    vector<unordered_map<int, int>> dead_touch(n+1);

    for(int i=0; i<=n; i++) dead_parents[i] = i;

    int ptr = 0;
    while(ptr < to_do.size()){
        int cand = to_do[ptr++];
        if(done[cand] || scc_counter[cand] != 1) continue;
        done[cand] = 1;

        for(auto u: colourGroup[cand]){
            dead_active[u] = 1;
            dead_parents[u] = u;
            dead_sizes[u] = 1;
            dead_touch[u].clear();
        }

        for(auto u: colourGroup[cand]){
            for(auto [c, v]: graph[u]){
                if(done[c] && dead_active[v]){
                    dead_unite(u, v, dead_parents, dead_sizes, dead_touch, done, dsu_parents, dsu_sizes, scc_counter, to_do);
                }
            }
        }

        for(auto u: colourGroup[cand]){
            int root = dead_find(u, dead_parents);

            for(auto [c, v]: graph[u]){
                if(!done[c]) add_touch(root, c, v, dead_parents, dead_touch, done, dsu_parents, dsu_sizes, scc_counter, to_do);
            }
        }
    }

    //-----------------------------
    bool good = 1;
    for(int i=1; i<=k; i++) if(!done[i]) good = 0;

    if(good) cout<<"TAK"; else cout<<"NIE";
    cout<<'\n';
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cout.tie(0); cin.tie(0);
 
    int sets; cin>>sets;
    while(sets--){
        solve();
    }
    return 0;
}