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
#include <iostream>
#include <queue>
#include <vector>

struct solve {
    int n, m, k, log_n;
    std::vector<int> color, depth, low, color_lca, indeg;
    std::vector<bool> visited;
    std::vector<std::vector<int>> graph, jmp, chrono;

    solve() {
        input();
        pre_dfs(1, 0);
        pre_lca();
        chrono_dfs(1);
        bool ans = toposort();
        std::cout << (ans ? "TAK" : "NIE") << '\n';
    }

    bool toposort() {
        //for (int v = 1; v <= k; v++) for (auto w : chrono[v]) std::cerr << v << " -> " << w << '\n';
        for (int v = 1; v <= k; v++) for (auto w : chrono[v]) indeg[w]++;
        std::queue<int> qu;
        for (int v = 1; v <= k; v++) if (!indeg[v]) qu.push(v);
        int sorted = 0;
        while (!qu.empty()) {
            int v = qu.front(); qu.pop();
            sorted++;
            for (auto w : chrono[v]) {
                indeg[w]--;
                if (!indeg[w]) qu.push(w);
            }
        }
        return sorted == k;
    }

    void chrono_dfs(int v) {
        visited[v] = true;
        for (auto w : graph[v]) if (!visited[w]) {
            //std::cerr << "v: " << v << " w: " << w << ' ';

            bool safe = color[w] == color[v] || w == color_lca[color[w]];
            if (!safe) chrono[color[w]].push_back(color[v]);
            //    (low[w] <= depth[color_lca[color[w]]] && depth[color_lca[color[w]]] < depth[color_lca[color[v]]]);
            //if (safe) std::cerr << "safe\n";

            //if (!safe) {
            //    if (low[w] > depth[color_lca[color[w]]]) {
            //        chrono[color[w]].push_back(color[v]);
            //        std::cerr << color[w] << " -> " << color[v] << "\n";
            //    }
            //    else {
            //        if (depth[color_lca[color[w]]] == depth[color_lca[color[v]]]) {
            //            if (color[color_lca[color[w]]] == color[w]) {
            //                chrono[color[v]].push_back(color[w]);
            //                std::cerr << color[v] << " -> " << color[w] << "\n";
            //            }
            //            else if (color[color_lca[color[w]]] == color[v]) {
            //                chrono[color[w]].push_back(color[v]);
            //                std::cerr << color[w] << " -> " << color[v] << "\n";
            //            }
            //        }
            //        else if (depth[color_lca[color[w]]] > depth[color_lca[color[v]]]) {
            //            chrono[color[v]].push_back(color[w]);
            //            chrono[color[w]].push_back(color[v]);
            //            std::cerr << "sprzeczność\n";
            //            //sprzeczność
            //        }
            //    }
            //}
            chrono_dfs(w);
            //bool safe = color[w] == color[v] || w == color_lca[color[w]] ||
            //    (low[w] <= depth[color_lca[color[w]]] && depth[color_lca[color[w]]] < depth[color_lca[color[v]]]);
            
            //std::cerr << "v: " << v << " w: " << w << ' ';
            //if (safe) std::cerr << "safe\n";

            //if (!safe) {
            //    if (low[w] = depth[color_lca[color[w]]] && color[color_lca[color[w]]] == color[w]) {
            //        chrono[color[v]].push_back(color[w]);
            //    }
            //    else chrono[color[w]].push_back(color[v]);

            //    if (low[w] = depth[color_lca[color[w]]] && color[color_lca[color[w]]] == color[w]) std::cerr << color[v] << " -> " << color[w] << "\n";
            //    else std::cerr << color[w] << " -> " << color[v] << "\n";
            //}
        }
    }

    void pre_lca() {
        for (int k = 1; k <= log_n; k++) for (int v = 1; v <= n; v++) {
            jmp[v][k] = jmp[jmp[v][k-1]][k-1];
        }
        for (int v = 1; v <= n; v++) {
            if (!color_lca[color[v]]) color_lca[color[v]] = v;
            else color_lca[color[v]] = lca(color_lca[color[v]], v);
            //std::cerr << "v: " << v << " color: " << color[v] << " lca: " << color_lca[color[v]] << '\n';
        }
        //std::cerr << "color lca: "; for (int v = 1; v <= k; v++) std::cerr << color_lca[v] << ' '; std::cerr << '\n';
    }

    int lca(int v, int w) {
        if (depth[v] < depth[w]) std::swap(v, w);
        //std::cerr << "lca " << v << ' ' << w << '\n';
        for (int k = log_n; k >= 0; k--) {
            if (depth[jmp[v][k]] >= depth[w]) v = jmp[v][k];
            if (depth[v] == depth[w]) break;
        }

        //std::cerr << "same depth " << v << ' ' << w << '\n';
        if (v == w) return v;

        for (int k = log_n; k >= 0; k--) {
            if (jmp[v][k] != jmp[w][k]) {
                v = jmp[v][k];
                w = jmp[w][k];
            }
        }

        //std::cerr << "one below " << v << ' ' << w << " lca " << jmp[v][0] << '\n';
        return jmp[v][0];
    }

    void pre_dfs(int v, int p) {
        low[v] = depth[v] = depth[p] + 1;
        jmp[v][0] = p;
        for (auto w : graph[v]) {
            if (!depth[w]) {
                pre_dfs(w, v);
                //low[v] = std::min(low[v], low[w]);
            }
            //else low[v] = std::min(low[v], depth[w]);
        }
    }

    void input() {
        std::cin >> n >> m >> k;
        log_n = 1; while ((1 << log_n) < n) log_n++;

        color = std::vector<int>(n+1); depth = std::vector<int>(n+1); low = std::vector<int>(n+1);
        color_lca = std::vector<int>(k+1); indeg = std::vector<int>(k+1); visited = std::vector<bool>(n+1);
        graph = std::vector<std::vector<int>>(n+1); jmp = std::vector<std::vector<int>>(n+1, std::vector<int>(log_n+1));
        chrono = std::vector<std::vector<int>>(k+1);

        for (int i = 1; i <= n; i++) std::cin >> color[i];
        for (int i = 0; i < m; i++) {
            int a, b; std::cin >> a >> b;
            graph[a].push_back(b);
            graph[b].push_back(a);
        }
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--) solve();

    return 0;
}