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

const int base = 1 << 20;
int rep[base];
int sajz[base];
int part[base]; //id danej partii
int amount[base]; //max amount of each color
vector<int> tree[base];

int rep_rm[base]; //reprezentant dla usuwanych spojnych
map<int, int> mapa[base]; //tutaj jest spis wszystkich unikalnych krawedzi

//fau stuff
int Find(int a){
    if(rep[a] == a) return a;
    return rep[a] = Find(rep[a]);
}

void Union(int a, int b){
    a = Find(a); b = Find(b);
    if(a == b) return;
    if(sajz[a] < sajz[b]) swap(a, b);
    sajz[a] += sajz[b];
    rep[b] = a;
}

//building graph stuff
bool vis[base];
int temp_odnos[base];
bool already_used[base];
void pre_dfs(int v, int p, int nr_parti){
    vis[v] = true;
    for(auto x: tree[v]){
        if(!vis[x] && part[x] == nr_parti){
            Union(v, x);
            pre_dfs(x, v, nr_parti);
        }
        else if(part[x] != nr_parti)
            mapa[nr_parti][Find(x)] = 1;
    }
}

//fau dla usuwanych spojnych
int Find_rm(int a){
    if(rep_rm[a] == a) return a;
    return rep_rm[a] = Find_rm(rep_rm[a]);
}

void Union_rm(int a, int b){
    a = Find_rm(a); b = Find_rm(b);
    if(a == b) return;
    if(mapa[a].size() < mapa[b].size()) swap(a, b);
    for(auto x: mapa[b]) mapa[a][Find(x.first)] = 1;
    mapa[b].clear();
    rep_rm[b] = a;
}

void clear_data(int n, int m, int k){
    n = max(n, max(m, k));
    for(int i = 0; i <= n; i++){
        rep[i] = -1; sajz[i] = -1;
        part[i] = 0; amount[i] = 0;
        tree[i].clear();
        already_used[i] = false;
        vis[i] = false;
        rep_rm[i] = 0; mapa[i].clear();
    }
}

int main(){

    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    int t; cin >> t;
    while(t--){
        int ile_parti = 0;
        int n, m, k; cin >> n >> m >> k;
        for(int i = 1; i <= n; i++){
            cin >> part[i];
            if(amount[part[i]] == 0) ile_parti++;
            amount[part[i]]++;
        }
        for(int i = 0; i < m; i++){
            int a, b; cin >> a >> b;
            tree[a].push_back(b);
            tree[b].push_back(a);
        }

        for(int i = 1; i <= n; i++){ sajz[i] = 1; rep[i] = i; }
        for(int c = 1; c <= k; c++) rep_rm[c] = c;
        for(int i = 1; i <= n; i++){
            if(!vis[i]) pre_dfs(i, 0, part[i]);
        }

        queue<int> covered;
        for(int i = 1; i <= n; i++){
            if(sajz[Find(i)] == amount[part[i]] && !already_used[part[i]]){
                covered.push(part[i]);
                already_used[part[i]] = true;
            }
        }

        int solved_ones = 0;
        while(!covered.empty()){
            int nr_parti = covered.front(); covered.pop();
            solved_ones++;

            vector<int> temp_u;
            for(auto x: mapa[nr_parti]){
                if(already_used[part[x.first]]) temp_u.push_back(part[x.first]);
            }
            for(auto x: temp_u) Union_rm(nr_parti, x);
            nr_parti = Find_rm(nr_parti);

            for(auto x: mapa[nr_parti]){
                if(!already_used[part[x.first]])
                    temp_odnos[part[x.first]] = Find(x.first);
            }
            for(auto x: mapa[nr_parti]){
                if(already_used[part[Find(x.first)]]) continue;
                Union(x.first, temp_odnos[part[x.first]]);
                if(sajz[Find(x.first)] == amount[part[x.first]] && !already_used[part[x.first]]){
                    covered.push(part[x.first]);
                    already_used[part[x.first]] = true;
                }
            }
        }

        if(solved_ones == ile_parti) cout << "TAK\n";
        else cout << "NIE\n";
        clear_data(n, m, k);
    }

    return 0;
}