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

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto a : (b))
#define repIn2(a, b, c) for(auto [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define int long long
#define ld long double
#define pb push_back

using namespace std;
#define rg ranges

int n, m, k;
vector<vector<int>> g, whereWho;
vector<unordered_map<int, int>> g2;
vector<int> rep, repSz, repWho, cntWho;

int fuFind(int x) { return rep[x] == x ? x : rep[x] = fuFind(rep[x]); }
void fuUnion(int a, int b) {
    a = fuFind(a);
    b = fuFind(b);
    if(a == b) return;
    rep[a] = b;
    repSz[b] += repSz[a];
}

void solve() {
    cin >> n >> m >> k;
    DC << n << m << k << '\n';
    g.clear(); g.resize(n + 1);
    whereWho.clear(); whereWho.resize(k + 1);
    g2.clear(); g2.resize(n + 1);
    rep.resize(n + 1);
    repSz.resize(n + 1);
    repWho.resize(n + 1);
    cntWho.resize(k + 1);
    rep(i, 0, k + 1) cntWho[i] = 0;
    cntWho[0] = -1;
    rep(i, 1, n + 1) rep[i] = i, repSz[i] = 1, cin >> repWho[i], cntWho[repWho[i]]++, whereWho[repWho[i]].pb(i);
    int a, b;
    queue<int> toProc;
    rep(i, 0, m) {
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
        if(repWho[fuFind(a)] == repWho[fuFind(b)] && fuFind(a) != fuFind(b)) {
            fuUnion(a, b);
            a = fuFind(a);
            if(repSz[a] == cntWho[repWho[a]]) toProc.push(a);
        }
    }
    rep(i, 0, n + 1) if(rep[i] == i && repSz[i] == 1 && cntWho[repWho[i]] == 1) toProc.push(i);
    repIn(i, cntWho) if(!i) k--;
    while(toProc.size()) {
        auto x = toProc.front();
        toProc.pop();
        k--;
        assert(x == rep[x]);
        unordered_set<int> brethren;
        repIn(v, whereWho[repWho[x]]) repIn(u, g[v]) brethren.insert(fuFind(u));
        brethren.erase(x);
        repWho[x] = 0;
        repIn(i, brethren) if(!repWho[i] && g2[i].size() > g2[x].size()) swap(g2[i], g2[x]);
        repIn(i, brethren) {
            if(repWho[i] == 0) {
                repIn2(wh, vu, g2[i]) {
                    if(!repWho[fuFind(vu)]) continue;
                    if(g2[x][wh] && fuFind(g2[x][wh]) != fuFind(vu)) {
                        fuUnion(g2[x][wh], vu);
                        vu = fuFind(vu);
                        g2[x][wh] = vu;
                        if(repSz[vu] == cntWho[repWho[vu]]) toProc.push(vu);
                    }
                    else g2[x][wh] = vu;
                }
                g2[i].clear();
                fuUnion(i, x);
            }
            else {
                auto vu = i;
                auto wh = repWho[i];
                if(!repWho[fuFind(vu)]) continue;
                if(g2[x][wh] && fuFind(g2[x][wh]) != fuFind(vu)) {
                    fuUnion(g2[x][wh], vu);
                    vu = fuFind(vu);
                    g2[x][wh] = vu;
                    if(repSz[vu] == cntWho[repWho[vu]]) toProc.push(vu);
                }
                else g2[x][wh] = vu;
            }
        }
    }
    cout << (k ? "NIE" : "TAK") << '\n';
}

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int t;
    cin >> t;
    while(t--) solve();
}