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
#include <bits/stdc++.h>

using namespace std;

#define int long long

int n, m, k;
vector<vector<int>> edges;
vector<int> votes;
vector<int> vote_counts, vote_positions;
vector<bool> visited, votes_done;

int count_dfs(int cn, int vote){
    int cnt = 0;
    if(votes[cn] == vote) cnt++;
    visited[cn] = 1;
    for(int nn : edges[cn]){
        if(visited[nn]) continue;
        if(votes[nn] != vote and !votes_done[votes[nn]]) continue;
        cnt += count_dfs(nn, vote);
    }
    return cnt;
}

void solve(){
    cin>>n>>m>>k;
    votes.resize(n + 1);
    edges.assign(n + 1, {});
    vote_counts.assign(k + 1, 0);
    vote_positions.assign(k + 1, 0);
    votes_done.assign(k+1, 0);
    for(int i = 1; i<=n; i++){
        cin>>votes[i];
        vote_counts[votes[i]]++;
        vote_positions[votes[i]] = i;
    }
    for(int i = 0; i<m; i++){
        int a, b; cin>>a>>b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    vector<int> order;
    for(int i = 0; i<k; i++) order.push_back(i + 1);
    random_shuffle(order.begin(), order.end());
    int done_v = 0;
    for(int i = 1; i<=k; i++){
        if(vote_counts[i] == 0){
            done_v++;
            votes_done[i] = 1;
        }
    }
    bool end = true;

    while(end){
        end = false;
        for(int val : order){
            if(votes_done[val]) continue;
            visited.assign(n + 1, 0);
            int count = count_dfs(vote_positions[val], val);
            if(count == vote_counts[val]){
                done_v++;
                votes_done[val] = 1;
                end = true;
            }
        }
    }

    if(done_v == k) cout<<"TAK"<<endl;
    else cout<<"NIE"<<endl;
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int t; cin>>t;
    while(t--) solve();
    return 0;
}