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


class Graph{
private:
    int n, m, k;
    vector<vector<int>> edge;
    vector<map<int, int>> neighbour;
    vector<int> leader;
    vector<int> color;
    vector<int> sizes;
    vector<int> zones, fz;
    priority_queue<int> next;

public:
    Graph(int n, int m, int k): n(n), m(m), k(k), edge(n+1), neighbour(n+1), leader(n+1), color(n+1), sizes(n+1, 1), zones(k+1), fz(k+1){
        for(int i = 0; i <= n; i++){
            leader[i] = i;
        }
    };

    int find(int v){
        if(leader[v] != v){
            leader[v] = find(leader[v]);
        }
        return leader[v];
    }

    void unite_special(int v, int u){
        for(auto [c, w]: neighbour[u]){
            if(c == 0){
                continue;
            }
            if(neighbour[v].find(c) != neighbour[v].end()){
                unite(neighbour[v][c], w);
            }else{
                neighbour[v][c] = u;
            }
        }
    }

    void unite(int v, int u, bool flag = false){
        v = find(v);
        u = find(u);
        if(u == v){
            return;
        }
        if(sizes[u] > sizes[v]){
            swap(u, v);
        }
        leader[u] = v;
        sizes[v] += sizes[u];
        for(auto w: edge[u]){
            edge[v].push_back(w);
        }
        if(color[u] != 0){
            zones[color[u]]--;
        }
        if(zones[color[v]] == 1){
            next.push(color[v]);
        }
        if(fz[color[v]] == u){
            fz[color[v]] = v;
        }
        if(flag){
            unite_special(v, u);
        }
    }

    void init(){
        for(int i = 1; i <= n; i++){
            cin >> color[i];
            zones[color[i]]++;
        }
        for(int i = 1; i <= m; i++){
            int u, v;
            cin >> u >> v;
            edge[u].push_back(v);
            edge[v].push_back(u);
        }
        for(int i = 1; i <= n; i++){
            if(find(i) != i){
                continue;
            }
            for(int j = 0; j < edge[i].size(); j++){
                int u = edge[i][j];
                int w = find(u);
                if(color[i] == color[w]){
                    unite(i, u);
                }
            }
        }
    }

    void calc(){
        for(int i = 1; i <= n; i++){
            if(fz[color[i]] == 0){
                fz[color[i]] = i;
            }
        }
        for(int i = 1; i <= k; i++){
            if(zones[i] == 1){
                next.push(i);
            }
        }
        while(!next.empty()){
            auto z = next.top();
            next.pop();
            int v = fz[z];
            v = find(v);
            if(color[v] == 0){
                continue;
            }
            color[v] = 0;
            vector<int> edge_zero;
            for(int j = 0; j < edge[v].size(); j++){
                int w = edge[v][j];
                if(color[w]  == 0){
                    edge_zero.push_back(w);
                    continue;
                }
                if(neighbour[v].find(color[w]) != neighbour[v].end()){
                    unite(neighbour[v][color[w]], w);
                    if(zones[color[find(w)]] == 1){
                        next.push(color[find(w)]);
                    }
                }else{
                    neighbour[v][color[w]] = w;
                }
            }
            for(auto w: edge_zero){
                // int w = edge[v][j];
                unite(v, w, true);
            }
    
        }
        for(int i = 1; i <= n; i++){
            if(color[i] != 0 and find(i) == i){
                cout << "NIE\n";
                return;
            }
        }
        cout << "TAK\n";
    }

};


void solve(){
    int n, m, k;
    cin >> n >> m >> k;
    Graph graph(n, m, k);
    graph.init();
    graph.calc();
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while(t--){
        solve();
    }
}