#include <algorithm>
#include <cstdio>
#include <numeric>
#include <vector>
#include <map>
#include <unordered_set>
#include <unordered_map>

#ifdef LOCAL
    #define dbg(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dbg(...)
#endif

using namespace std;

struct EdgeSystem {
    unordered_map<int, unordered_set<int>> edges;

    explicit EdgeSystem() = default;

    void join(EdgeSystem& other, const unordered_set<int>& relevant_colors, const unordered_set<int>& blankable_colors) {
        dbg("STARTING JOIN STATE\n");

        for (auto& [color, mySet] : edges) {
            dbg("Now have edges to color %2d:\n", color);
            for (auto& target: mySet) {
                dbg("%2d ", target+1);
            }
            dbg("\n");
        }
        dbg("----------------------\n");

        for (auto& [color, otherSet] : other.edges) {
            dbg("Joining edges to color %2d\n", color);
            int insert_color = color;
            if (!relevant_colors.contains(color) || blankable_colors.contains(color)) {
                dbg("Inserting old color %2d as color 0\n", color);
                insert_color = 0;
            }
            unordered_set<int>& mySet = edges[insert_color];
            dbg("__This set: \n");
            for (auto& target: mySet) {
                dbg("%2d ", target+1);
            }
            dbg("\n__Other set: \n");
            for (auto& target: otherSet) {
                dbg("%2d ", target+1);
            }

            // insert smaller set into larger
            if (mySet.size() < otherSet.size()) swap(mySet, otherSet);
            mySet.insert(otherSet.begin(), otherSet.end());
            dbg("\n__Result:\n");
            for (auto& target: mySet) {
                dbg("%2d ", target+1);
            }
            dbg("\n____________\n");
        }

        dbg("ENDING JOIN STATE\n");

        for (auto& [color, mySet] : edges) {
            dbg("Now have edges to color %2d:\n", color);
            for (auto& target: mySet) {
                dbg("%2d ", target+1);
            }
            dbg("\n");
        }
        dbg("----------------------\n");
        // other.edges.clear();
    }
};

struct UnionFinder {
private:
    vector<int> parent;
    vector<int> rank;

public:
    vector<int> node_colors;
    vector<int> color_counts;
    vector<int> color_examples;

    vector<EdgeSystem> edge_systems; // edge_systems[X].edges[Y] - set of edges to nodes of color Y from node X
    unordered_set<int> relevant_colors;
    unordered_set<int> blankable_colors;

    explicit UnionFinder(const int n_nodes, const int n_colors) : parent(n_nodes), rank(n_nodes, 0), node_colors(n_nodes), color_counts(n_colors, 0), color_examples(n_colors), edge_systems(n_nodes) {
        iota(parent.begin(), parent.end(), 0);
    }

    // find group id of node x
    int do_find(const int x) {
        if (parent[x] != x)
            parent[x] = do_find(parent[x]);
        return parent[x];
    }

    // join nodes x and y into one group
    void do_union(int x, int y) {
        x = do_find(x);
        y = do_find(y);
        dbg("    UNIONING GROUPS OF %d and %d\n", x+1, y+1);
        if (x == y) return;
        int color = node_colors[x];
        if (relevant_colors.contains(color)) {
            color_counts[color] -= 1;
            if (color_counts[color] == 1) {
                dbg("  COLOR %2d IS NOW BLANKABLE!\n", color);
                blankable_colors.insert(color);
            }
        }
        if (rank[x] < rank[y]) swap(x, y);
        parent[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
        dbg("      NEW GROUP ID: %d\n", x+1);
        edge_systems[x].join(edge_systems[y], relevant_colors, blankable_colors);
    }

    // turn group of node X into a blank node
    // this will:
    //  - do_union of it with any adjacent blank nodes
    //  - join all nodes of the same color connected to the new big blank
    void blank(const int color_to_blank) {
        int group_to_blank = do_find(color_examples[color_to_blank]);

        dbg("BLANKING COLOR %2d (group %2d)\n", color_to_blank, group_to_blank+1);

        relevant_colors.erase(color_to_blank);

        // UNION WITH ANY BLANK NODES

        unordered_set<int> blank_systems;
        vector<int> colors_to_erase;

        for (auto& [color, edges] : edge_systems[group_to_blank].edges) {
            if (!relevant_colors.contains(color) || blankable_colors.contains(color)) {
                dbg("JOINING WITH BLANK GROUP, FORMERLY COLOR %d\n", color);
                // color is blank
                for (auto& edge: edges) {
                    blank_systems.insert(do_find(edge));
                }
                colors_to_erase.push_back(color);
            }
        }
        for (auto& color: colors_to_erase) {
            edge_systems[group_to_blank].edges.erase(color);
        }

        for (auto& system: blank_systems) {
            do_union(group_to_blank, system);
        }

        int bigblank = do_find(group_to_blank);

        // WE ARE NOW UNIONED INTO ONE BIG BLANK. LET'S TRY TO CONNECT SOME NODES.

        for (auto& [color, edges]: edge_systems[bigblank].edges) {
            if (relevant_colors.contains(color)) {
                dbg("TRYING TO JOIN ANY NODES OF COLOR %2d\n", color);
                if (edges.size() < 2) {
                    dbg("  NOT ENOUGH NODES OF THIS COLOR.\n");
                    dbg("   (Only found edge to %2d)\n", (*edges.begin())+1);
                    continue;
                }
                vector<int> to_join;
                for (auto& edge: edges) {
                    to_join.push_back(edge);
                    dbg("  JOINING NODE: %2d\n", edge+1);
                }
                int focus = do_find(to_join[0]);
                for (int i = 1; i < to_join.size(); ++i) {
                    int nxt = do_find(to_join[i]);
                    if (focus != nxt) {
                        do_union(focus, nxt);
                        focus = do_find(focus);
                    }
                }
                dbg("  REMAINING COUNT OF COLOR %2d: %2d\n", color, color_counts[color]);
                // reduce the edge list for the future
                edge_systems[bigblank].edges[color] = unordered_set<int>({do_find(focus)});
            }
        }

        // AFTER CREATING THE MEGABLANK: GO THROUGH ALL COLORS WE HAVE EDGES TO
        //  FOR EACH COLOR:
        //   if no longer relevant: remove key
        //   if only has one edge: ignore
        //   if multiple edges: union all nodes. remove all edges. add edge with only the root.

    }
};

int main() {
    int t;
    scanf("%d", &t);

    for (int ti = 0; ti < t; ++ti) {
        int n, m, k;
        scanf("%d %d %d", &n, &m, &k);

        UnionFinder union_finder(n, k+1);

        for (int i = 0; i < n; ++i) {
            int color;
            scanf("%d", &color);
            union_finder.node_colors[i] = color;
            union_finder.color_counts[color] += 1;
            union_finder.relevant_colors.insert(color);
            union_finder.color_examples[color] = i;
        }

        dbg("REVELANT COLORS:\n");
        for (auto& color: union_finder.relevant_colors) {
            dbg("%2d: %2d\n", color, union_finder.color_counts[color]);
        }

        for (auto& color: union_finder.relevant_colors) {
            if (union_finder.color_counts[color] == 1) {
                dbg("COLOR %2d IS BLANKABLE FROM THE START!\n", color);
                union_finder.blankable_colors.insert(color);
            }
        }

        for (int i = 0; i < m; ++i) {
            int a, b;
            scanf("%d %d", &a, &b);
            // -1 to stay 0-indexed
            a -= 1;
            b -= 1;
            int a_color = union_finder.node_colors[a];
            int b_color = union_finder.node_colors[b];

            if (a_color == b_color) {
                union_finder.do_union(a, b);
            } else {
                int a_root = union_finder.do_find(a);
                int b_root = union_finder.do_find(b);
                union_finder.edge_systems[a_root].edges[b_color].insert(b_root);
                union_finder.edge_systems[b_root].edges[a_color].insert(a_root);
            }
        }

        dbg("---------- STARTING OPERATION ----------\n");

        bool broken = false;

        while (!union_finder.blankable_colors.empty()) {
            if (union_finder.blankable_colors.size() == union_finder.relevant_colors.size()) {
                broken = true;
                break;
            }
            int color_to_blank = *union_finder.blankable_colors.begin();
            dbg("NEXT COLOR TO BLANK: %2d\n", color_to_blank);
            union_finder.blankable_colors.erase(color_to_blank);
            union_finder.blank(color_to_blank);
        }

        if (!broken && !union_finder.relevant_colors.empty()) {
            printf("NIE\n");
            dbg("COULD NOT BLANK WHOLE GRAPH\n");
            for (auto& color: union_finder.relevant_colors) {
                dbg("COLOR LEFT: %2d\n", color);
            }
        } else {
            printf("TAK\n");
        }
    }

    return 0;
}