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

using namespace std;
#define vec vector

void dfs(int u, vec<bool> &vis, vec<vec<int>> &spojne, int curcolor, vec<int> &a, vec<vec<int>> &g, vec<int> &w) {
    vis[u] = true;
    w[u] = spojne.size() - 1;

    for (int edge: g[u]) {
        if (!vis[edge] and a[edge] == curcolor) {
            dfs(edge, vis, spojne, curcolor, a, g, w);
        }
        else if (a[edge] != curcolor) {
            spojne.back().push_back(edge);
        }
    }
}

void visdfs(int u, vec<int> &colors, vec<vec<int>> &g, int col) {
    colors[u]  = col;
    for (int edge: g[u]) {
        if (colors[edge] == -1) {
            visdfs(edge, colors, g, col);
        }
    }
}

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


        vec<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            a[i] -- ;
        }

        vec<vec<int>> g(n);
        for (int i = 0; i < m; i++) {
            int u, v; cin >> u >> v;
            u--;
            v--;
            g[u].push_back(v);
            g[v].push_back(u);
        }

        vec<vec<int>> g2;
        vec<int> col;
        vec<bool> vis(n);
        vec<int> w(n);
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                g2.push_back({});
                col.push_back(a[i]);
                dfs(i, vis, g2, a[i], a, g, w);
            }
        }
        
        vec<int> r(g2.size());
        for (int i = 0; i < g2.size(); i++) {
            for (int &el: g2[i]) {
                el = w[el];
            }
        }

        vec<int> colors(g2.size(), -1);
        int curcol = 0;
        for (int i = 0; i < g2.size(); i++) {
            if (colors[i] == -1) {
                visdfs(i, colors, g2, curcol);
                curcol ++;
            }
        }
        vec<int> colfor(k, -1);
        bool ok = true;
        for (int i = 0; i < g2.size(); i++) {
            if (colfor[col[i]] == -1) colfor[col[i]] = colors[i];
            else if (colfor[col[i]] != colors[i]) {
                ok = false;
                break;
            }
        }
        if (!ok) {
            cout << "NIE\n";
            continue;
        }

        

        for (int i = 0; i < g2.size(); i++) {
          unordered_map<int, int> cnts;
          unordered_set<int> vis;
          for (int edge : g2[i]) {
            if (vis.count(edge)) continue;
            cnts[col[edge]]++;
            vis.insert(edge);
          }

            for (int edge: g2[i]) {
                if (cnts[col[edge]] >= 2) r[edge] ++;
            }
        }
        queue<int> to;

        for (int i = 0; i < g2.size(); i++) {
            if (r[i] == 0) {
                to.push(i);
            }
        }


        while (!to.empty()) {
          int u = to.front();
          to.pop();
          unordered_map<int, int> cnts;
          unordered_set<int> vis;
          for (int edge : g2[u]) {
            if (vis.count(edge)) continue;
            cnts[col[edge]]++;
            vis.insert(edge);
          }

          for (int edge : g2[u]) {
            if (cnts[col[edge]] >= 2) {
                r[edge] --;
                if (r[edge] == 0) to.push(edge);
            }
          }
        }
        bool any = false;
        for (int i = 0; i < g2.size(); i++) if (r[i] != 0) any = true;
        if (any) cout << "NIE\n";
        else cout << "TAK\n";
    }
}