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

int n, m, k;
std::vector<std::vector<int>> g;
std::vector<int> party;
std::vector<std::vector<int>> party_members;
std::vector<bool> is_visited;
std::vector<int> is_visited_gen;
std::vector<int> party_members_visited;
std::vector<int> total_party_members;
int num_visited;
int gen;
bool reached_visited_same_party;

void dfs(int p, int x, std::vector<int>& vis)
{
    if (!is_visited[x])
        vis.push_back(x);
    is_visited_gen[x] = gen;
    for (int neighbor : g[x])
        if (is_visited_gen[neighbor] != gen)
        {
            if ((!is_visited[neighbor] && party[neighbor] == p) || (is_visited[neighbor] && party[neighbor] == -1))
                dfs(p, neighbor, vis);
            else if (is_visited[neighbor] && party[neighbor] == p)
                reached_visited_same_party = true;
        }
}

void solve()
{
    std::cin >> n >> m >> k;
    g.clear();
    g.resize(n);
    party.resize(n);
    is_visited.resize(n);
    is_visited_gen.resize(n);
    num_visited = 0;
    gen = 0;
    party_members_visited.resize(k);
    total_party_members.resize(k);
    party_members.clear();
    party_members.resize(k);
    for (int i = 0; i < k; ++i)
    {
        party_members_visited[i] = 0;
        total_party_members[i] = 0;
    }
    for (int i = 0; i < n; ++i)
    {
        int i_party;
        std::cin >> i_party;
        --i_party;
        party[i] = i_party;
        party_members[i_party].push_back(i);
        is_visited[i] = false;
        is_visited_gen[i] = 0;
        ++total_party_members[i_party];
    }
    for (int i = 0; i < m; ++i)
    {
        int u, v;
        std::cin >> u >> v;
        --u;
        --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    while (num_visited < n)
    {
        bool expanded = false;
        for (int i = 0; i < n; ++i)
            if (!is_visited[i])
            {
                std::vector<int> vis;
                int p = party[i];
                ++gen;
                reached_visited_same_party = false;
                dfs(p, i, vis);
                if (!party_members_visited[p] || reached_visited_same_party)
                {
                    expanded = true;
                    for (int x : vis)
                    {
                        is_visited[x] = true;
                        ++party_members_visited[p];
                        ++num_visited;
                    }
                    if (party_members_visited[p] == total_party_members[p])
                        for (int x : party_members[p])
                            party[x] = -1;
                }
            }
        if (!expanded)
            break;
    }
    std::cout << (num_visited == n ? "TAK" : "NIE") << std::endl;
}

int main()
{
    int t;
    std::cin >> t;
    for (int i = 0; i < t; ++i)
        solve();
    return 0;
}

/*

1
3 2 2
1 2 2
1 2
1 3


1
5 5 3
1 2 1 1 3
1 2
2 3
3 4
4 5
5 1


3
5 5 3
1 2 1 1 3
1 2
2 3
3 4
4 5
5 1
4 3 3
2 2 2 2
1 2
1 3
1 4
4 3 2
1 2 1 2
1 2
2 3
3 4


*/