#include <cstdio>
#include <cassert>

#include <vector>
#include <map>

struct uf_t {
    uf_t* parent;
    int rank;
    int vertex;
};

struct edge_t {
    int target;
    int next_edge;
};

struct vertex_t {
    int first_edge;
    int who_won;
    uf_t wildcard_rep;
    std::map<int, uf_t> party_to_rep;
};

struct party_t {
    int first_member;
    int connected_components;
};

static const int WILDCARD_PARTY = -1;

// This is a thing of beauty
static uf_t* uf_find(uf_t* p) {
    assert(p != nullptr);

    if (p->parent == nullptr) {
        return p;
    }

    // TODO: Avoid recursion by reversing in place
    p->parent = uf_find(p->parent);
    return p->parent;
}

// Returns true if pa and pb weren't already in the same component
static bool uf_union(uf_t* pa, uf_t* pb) {
    uf_t* pa_root = uf_find(pa);
    uf_t* pb_root = uf_find(pb);
    if (pa_root == pb_root) {
        return false; // Fast path - nothing to do
    }
    if (pa_root->rank > pb_root->rank) {
        pb_root->parent = pa_root;
    } else if (pa_root->rank < pb_root->rank) {
        pa_root->parent = pb_root;
    } else {
        pb_root->parent = pa_root;
        pa_root->rank += 1;
    }
    return true;
}

// Can use it to either only merge vertices of the same color, or with wildcards
static void vertex_multi_union(std::vector<int>& candidates, std::vector<party_t>& parties, vertex_t& va, vertex_t& vb, int b) {
    if (&va == &vb) {
        // fprintf(stderr, "    Skipping mult-union because vertices are the same\n");
        return;
    }

    assert(va.party_to_rep.size() <= vb.party_to_rep.size());

    for (auto&& [party_idx, uf] : va.party_to_rep) {
        // fprintf(stderr, "    Multi-unifying party %d\n", party_idx+1);
        auto [it, inserted] = vb.party_to_rep.try_emplace(party_idx, uf_t{nullptr, 0, b});
        if (uf_union(&uf, &it->second)) {
            // fprintf(stderr, "     Performed a successful union\n");
            if (inserted) {
                // fprintf(stderr, "      Wildcard did not have the party already, not decreasing the counter\n");
            } else if (--parties[party_idx].connected_components == 1) {
                // fprintf(stderr, "      Adding the party to candidates\n");
                candidates.push_back(party_idx);
            } else {
                // fprintf(stderr, "      The counter of the party decreased to %d\n", parties[party_idx].connected_components);
            }
        } else {
            // fprintf(stderr, "     Parties already unified\n");
        }
    }
}

static bool solve() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);

    // assert(n <= 100 * 1000);
    // assert(m <= 100 * 1000);
    // assert(k <= 100 * 1000);

    std::vector<vertex_t> vertices;
    std::vector<edge_t> edges;
    std::vector<party_t> parties;
    std::vector<int> party_next_member;

    vertices.reserve(n);
    edges.reserve(2 * m);
    parties.reserve(k);
    party_next_member.reserve(n);

    for (int i = 0; i < k; i++) {
        parties.push_back(party_t{
            .first_member = -1,
            .connected_components = 0,
        });
    }

    for (int i = 0; i < n; i++) {
        int who_won;
        scanf("%d", &who_won);
        assert(who_won > 0);
        who_won -= 1;
        assert(who_won < k);

        vertices.push_back(vertex_t{
            .first_edge = -1,
            .who_won = who_won,
            .wildcard_rep = uf_t{nullptr, 0, i},
            .party_to_rep = {},
        });
        vertices.back().party_to_rep.insert({who_won, uf_t{nullptr, 0, i}});

        party_next_member.push_back(parties[who_won].first_member);
        parties[who_won].first_member = i;
        parties[who_won].connected_components++;
    }

    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        assert(a > 0);
        assert(b > 0);
        a -= 1;
        b -= 1;

        assert(a < n);
        assert(b < n);

        edges.push_back(edge_t{
            .target = b,
            .next_edge = vertices[a].first_edge,
        });
        vertices[a].first_edge = 2 * i + 0;

        edges.push_back(edge_t{
            .target = a,
            .next_edge = vertices[b].first_edge,
        });
        vertices[b].first_edge = 2 * i + 1;
    }

    std::vector<int> candidate_parties;
    candidate_parties.reserve(n);

    // Create the initial per-color connected components
    // fprintf(stderr, "Looking for parties with zero or one city\n");
    for (int i = 0; i < k; i++) {
        // If there is at least one successfully processed party with non-zero
        // cities, we can say that zero-city parties are legit because they
        // could have just entered any city that was covered by the last
        // party that had a tour.
        // Add these parties to the list of parties to process, those will be
        // no-op.
        if (parties[i].connected_components <= 1) {
            // fprintf(stderr, " Adding party %d to candidates\n", i+1);
            candidate_parties.push_back(i);
        }
    }
    // fprintf(stderr, "Tying initial cities together\n");
    for (int i = 0; i < n; i++) {
        // fprintf(stderr, " Visiting vertex %d\n", i+1);
        auto& my_vert = vertices[i];
        for (int e = vertices[i].first_edge; e != -1; e = edges[e].next_edge) {
            // fprintf(stderr, "  Visiting neighbor %d\n", edges[e].target+1);
            if (edges[e].target <= i) {
                // fprintf(stderr, "   Skipping, the pair will be or was processed (bidirectionality)\n");
                continue;
            }
            auto& target_vert = vertices[edges[e].target];
            if (my_vert.who_won == target_vert.who_won) {
                vertex_multi_union(candidate_parties, parties, my_vert, target_vert, edges[e].target);
            } else {
                // fprintf(stderr, "   Party does not match, %d vs. %d\n", my_vert.who_won+1, target_vert.who_won+1);
            }
        }
    }

    int parties_processed = 0;
    while (!candidate_parties.empty()) {
        parties_processed++;
        const int curr_party = candidate_parties.back();
        candidate_parties.pop_back();

        // fprintf(stderr, "Processing party: %d\n", curr_party + 1);

        for (int v = parties[curr_party].first_member; v != -1; v = party_next_member[v]) {
            // fprintf(stderr, " Visiting vertex %d\n", v+1);
            auto& my_vert = vertices[v];
            my_vert.who_won = WILDCARD_PARTY;
            for (int e = vertices[v].first_edge; e != -1; e = edges[e].next_edge) {
                // fprintf(stderr, "  Visiting neighbor %d\n", edges[e].target+1);
                auto& target_vert = vertices[edges[e].target];
                if (target_vert.who_won == curr_party) {
                    // Connections are bidirectional, we will process this pair later
                    // when the other vertex becomes a wildcard
                    continue;
                }
                int my_wildcard_rep = uf_find(&my_vert.wildcard_rep)->vertex;
                if (target_vert.who_won == WILDCARD_PARTY) {
                    int target_wildcard_rep = uf_find(&target_vert.wildcard_rep)->vertex;
                    int giving_wildcard_rep, receiving_wildcard_rep;
                    if (vertices[my_wildcard_rep].party_to_rep.size()
                            <= vertices[target_wildcard_rep].party_to_rep.size()) {
                        giving_wildcard_rep = my_wildcard_rep;
                        receiving_wildcard_rep = target_wildcard_rep;
                    } else {
                        giving_wildcard_rep = target_wildcard_rep;
                        receiving_wildcard_rep = my_wildcard_rep;
                    }
                    // fprintf(stderr, "   Multi-union of wildcard %d with wildcard %d\n", giving_wildcard_rep+1, receiving_wildcard_rep+1);
                    vertex_multi_union(candidate_parties, parties, vertices[giving_wildcard_rep], vertices[receiving_wildcard_rep], receiving_wildcard_rep);
                    uf_union(&my_vert.wildcard_rep, &target_vert.wildcard_rep);
                    // fprintf(stderr, "   Union find chose %d as the new rep\n", uf_find(&my_vert.wildcard_rep)->vertex+1);
                    if (uf_find(&my_vert.wildcard_rep)->vertex != receiving_wildcard_rep) {
                        // fprintf(stderr, "    Swapping the sets as union find chose the other vertex\n");
                        std::swap(vertices[my_wildcard_rep].party_to_rep, vertices[target_wildcard_rep].party_to_rep);
                    } else {
                        // fprintf(stderr, "    No need to swap, union find chose correctly\n");
                    }
                } else {
                    // fprintf(stderr, "   Multi-union of non-wildcard %d with wildcard %d\n", edges[e].target+1, my_wildcard_rep+1);
                    vertex_multi_union(candidate_parties, parties, target_vert, vertices[my_wildcard_rep], my_wildcard_rep);
                }
            }
        }
    }

    // fprintf(stderr, "Processed vs. k: %d, %d\n", parties_processed, k);
    return parties_processed == k;
}

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

    while (t --> 0) {
        puts(solve() ? "TAK" : "NIE");
    }

    return 0;
}