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
#include <bits/stdc++.h>
using namespace std;
#define rep(a, b) for (int a = 0; a < (b); a++)
#define rep1(a, b) for (int a = 1; a <= (b); a++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int MOD = 1e9 + 7;

const int LIM = 1e5 + 7;
int V, E, k;

int col[LIM];
int colrepr[LIM];
int colcnt[LIM];
vector<int> graph[LIM];

int repr[LIM];
vector<int> group[LIM];
bool ishole[LIM];

int seencolv[LIM];
map<int, int> holemap[LIM];

vector<int> connectedcols;
void merge(int v1, int v2, bool holes) {
    v1 = repr[v1];
    v2 = repr[v2];
    if (v1 == v2) return;
    if (group[v1].size() < group[v2].size()) swap(v1, v2);
    for (int v: group[v2]) {
        repr[v] = v1;
        group[v1].push_back(v);
    }
    group[v2].clear();
    if (!holes && --colcnt[col[v1]] == 1) connectedcols.push_back(col[v1]);

    if (holes) {
        for (auto [c, v]: holemap[v2]) {
            auto it = holemap[v1].find(c);
            if (it == holemap[v1].end()) holemap[v1][c] = v;
            else merge(v, it->second, false);
        }
        holemap[v2].clear();
    }
}

void solve() {
    cin >> V >> E >> k;
    rep1(v, V) {
        cin >> col[v];
        colcnt[col[v]]++;
        colrepr[col[v]] = v;
    }
    rep1(v, V) if (colcnt[col[v]] == 1) connectedcols.push_back(col[v]);
    
    rep1(v, V) {
        repr[v] = v;
        group[v] = {v};
    }

    int v1, v2;
    rep(i, E) {
        cin >> v1 >> v2;
        graph[v1].push_back(v2);
        graph[v2].push_back(v1);
        if (col[v1] == col[v2]) merge(v1, v2, false);
    }

    while (!connectedcols.empty()) {
        int conncol = connectedcols.back();
        connectedcols.pop_back();
        int rv = repr[colrepr[conncol]];
        vector<int> foundcols;
        vector<int> holes;
        for (int v: group[rv]) for (int to: graph[v]) if (col[v] != col[to]) {
            to = repr[to];
            if (ishole[to]) holes.push_back(to);
            else {
                int seenv = seencolv[col[to]];
                if (seenv != 0) merge(to, seenv, false);
                else {
                    foundcols.push_back(col[to]);
                    seencolv[col[to]] = to;
                }
            }
        }

        for (int v: group[rv]) ishole[v] = true;
        for (int c: foundcols) {
            holemap[rv][c] = seencolv[c];
            seencolv[c] = 0;
        }
        for (int h: holes) merge(rv, h, true);
    }

    bool ok = true;
    rep1(v, V) ok &= ishole[v];
    cout << (ok ? "TAK" : "NIE") << "\n";

    connectedcols.clear();
    rep1(v, V) {
        col[v] = 0;
        graph[v].clear();
        repr[v] = 0;
        group[v].clear();
        ishole[v] = false;
        holemap[v].clear();
    }
    rep1(c, k) {
        colrepr[c] = 0;
        colcnt[c] = 0;
        seencolv[c] = 0;
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();

    return 0;
}