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

bool solve() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> color(n);
    for (int &x: color) cin >> x, x--;

    vector<vector<int>> adj(n);
    while (m--) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        if (a == b) continue;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vector<int> color_count(k);
    for (int x: color) color_count[x]++;

    vector<int> root(n);
    iota(begin(root), end(root), 0);

    vector<vector<int>> comp(n);
    for (int a = 0; a < n; a++) {
        comp[a].push_back(a);
    }

    vector<map<int,int>> neighbor_of_color(n);
    queue<pair<int,int>> todo;

    auto unite = [&](int a, int b) {
        a = root[a], b = root[b];
        if (a == b) return;

        if (comp[a].size() < comp[b].size()) swap(a, b);
        for (int c: comp[b]) {
            root[c] = a;
            comp[a].push_back(c);
        }

        if (color[a] < 0) {
            bool flip = neighbor_of_color[a].size() < neighbor_of_color[b].size();
            if (flip) swap(a, b);
            for (auto [x, c]: neighbor_of_color[b]) {
                if (neighbor_of_color[a].count(x)) {
                    todo.emplace(c, neighbor_of_color[a][x]);
                } else {
                    neighbor_of_color[a][x] = c;
                }
            }
            if (flip) swap(neighbor_of_color[a], neighbor_of_color[b]);
        } else {
            int x = color[a];
            if (--color_count[x] == 1) todo.emplace(a, -1);
        }
    };

    auto make_gray = [&](int a) {
        a = root[a];
        int x = color[a];
        set<int> grays;
        for (int b: comp[a]) {
            for (int c: adj[b]) {
                int y = color[c];
                if (y < 0) grays.insert(c);
                if (y == x || y < 0) continue;
                if (neighbor_of_color[a].count(y)) {
                    todo.emplace(c, neighbor_of_color[a][y]);
                } else {
                    neighbor_of_color[a][y] = c;
                }
            }
        }
        for (int b: comp[a]) color[b] = -1;
        for (int b: grays) todo.emplace(a, b);
    };

    for (int a = 0; a < n; a++) {
        for (int b: adj[a]) {
            if (color[a] == color[b]) todo.emplace(a, b);
        }
        if (color_count[color[a]] == 1) todo.emplace(a, -1);
    }

    while (!todo.empty()) {
        auto [a, b] = todo.front();
        todo.pop();
        if (b < 0) {
            make_gray(a);
        } else {
            assert((color[a] < 0) == (color[b] < 0));
            unite(a, b);
        }
    }

    return *max_element(begin(color), end(color)) < 0;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int tc; cin >> tc;
    while (tc--) {
        cout << (solve() ? "TAK" : "NIE") << '\n';
    }
}