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

using namespace std;

typedef long long ll;

vector<ll> a;
vector<ll> nbhs[100100];
unordered_map<ll, vector<ll>> groups;

ll r[100100];
ll h[100100];
ll s[100100];

ll r2[100100];

ll _find(ll v) {
    if(r[v] == v) {
        return v;
    }

    r[v] = _find(r[v]);
    return r[v];
}

void _union(ll v, ll u) {
    ll rv = _find(v);
    ll ru = _find(u);

    if(rv == ru) {
        return;
    }

    if(h[rv] > h[ru]) {
        r[ru] = rv;
        s[rv] += s[ru];
    } else if(h[rv] < h[ru]) {
        r[rv] = ru;
        s[ru] += s[rv];
    } else {
        r[ru] = rv;
        h[rv]++;
        s[rv] += s[ru];
    }
}

ll _find2(ll v) {
    if(r2[v] == v) {
        return v;
    }

    r2[v] = _find2(r2[v]);
    return r2[v];
}

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

    ll t;
    cin >> t;

    while(t--) {
        ll n, m, k;
        cin >> n >> m >> k;

        for(ll i = 0LL; i <= n; i++) {
            r[i] = i;
            h[i] = 1LL;
            s[i] = 1LL;
            r2[i] = i;
        }

        a.clear();
        a.push_back(-1);
        groups.clear();
        for(ll i = 1LL; i <= n; i++) {
            ll tmp;
            cin >> tmp;
            a.push_back(tmp);

            groups[tmp].push_back(i);
            nbhs[i].clear();
        }

        for(ll i = 0LL; i < m; i++) {
            ll u, v;
            cin >> u >> v;

            nbhs[u].push_back(v);
            nbhs[v].push_back(u);
        }

        vector<ll> q;
        for(auto i: groups) {
            ll color = i.first;
            for(auto v: i.second) {
                for(auto u: nbhs[v]) {
                    if(a[u] == color) {
                        _union(v, u);
                    }
                }

                if(s[_find(v)] == i.second.size()) {
                    q.push_back(color);
                }
            }
        }

        unordered_map<ll, bool> visited;
        map<ll, unordered_map<ll, ll>> groups_local;
        unordered_map<ll, ll> groups_local_size;
        ll pc = 0LL;
        for(ll i = 0LL; i < q.size(); i++) {
            ll color = q[i];

            if(visited[color]) {
                continue;
            }
            visited[color] = true;
            pc++;

            for(auto v: groups[color]) {
                for(auto u: nbhs[v]) {
                    if(!visited[a[u]]) {
                        continue;
                    }

                    ll rv = _find2(v);
                    ll ru = _find2(u);

                    if(rv == ru) {
                        continue;
                    }

                    if(groups_local_size[rv] < groups_local_size[ru]) {
                        swap(rv, ru);
                    }
                    r2[ru] = rv;

                    for(auto e: groups_local[ru]) {
                        ll c = e.first;
                        ll ru2 = _find(e.second);

                        if(groups_local[rv].count(c)) {
                            ll rv2 = _find(groups_local[rv][c]);
                            if(rv2 != ru2) {
                                _union(rv2, ru2);
                                ll rn = _find(rv2);
                                groups_local[rv][c] = rn;

                                if(s[rn] == groups[c].size()) {
                                    q.push_back(c);
                                }
                            }
                        } else {
                            groups_local[rv][c] = ru2;
                        }
                    }
                    groups_local_size[rv] += groups_local_size[ru];
                    groups_local_size[ru] = 0LL;
                    groups_local[ru].clear();
                }
            }

            for(auto v: groups[color]) {
                ll r2_v = _find2(v);
                for(auto u: nbhs[v]) {
                    if(visited[a[u]]) {
                        continue;
                    }

                    ll nbh_c = a[u];
                    ll nbh_r = _find(u);

                    if(groups_local[r2_v].count(nbh_c)) {
                        ll r = _find(groups_local[r2_v][nbh_c]);
                        if(r != nbh_r) {
                            _union(r, nbh_r);
                            groups_local[r2_v][nbh_c] = _find(r);

                            if(s[_find(r)] == groups[nbh_c].size()) {
                                q.push_back(nbh_c);
                            }
                        }
                    } else {
                        groups_local[r2_v][nbh_c] = nbh_r;
                        groups_local_size[r2_v]++;
                    }
                }
            }
        }

        cout << (pc == groups.size() ? "TAK" : "NIE") << "\n";
    }

    return 0;
}