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
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN = 1e5+5;
vector<int> cnt,color,sz,rep,v[MAXN],by_color[MAXN];
vector<map<int,int>> mp;
vector<bool> used;
queue<int> q;

int Find(int x){
    if(rep[x]==x) return x;
    return rep[x] = Find(rep[x]);
}

void Union(int x, int y){
    x = Find(x); y = Find(y);
    if(x==y) return;
    if(sz[x] > sz[y]) swap(x,y);
    rep[x] = y;
    sz[y] += sz[x];
    if(used[x]){
        for(auto [key, val]: mp[x]){
            if(mp[y].find(key) == mp[y].end()) mp[y][key] = val;
            else{
                int a = mp[y][key];
                Union(a, val);
                mp[y][key] = Find(a);
            }
        }
    }
    else{
        if(sz[y] == cnt[color[y]]){
            q.push(color[y]);
            sz[y]--;
        }
    }

}

void solve(){

    int n,m,k; cin >> n >> m >> k;
    cnt = vector<int>(k+1,0);
    color = vector<int>(n+1,0); rep = vector<int>(n+1,0); sz = vector<int>(n+1,0);
    used = vector<bool>(n+1,false);
    mp = vector<map<int,int>>(n+1);
    set<int> distinct;
    for(int i=1;i<=k;i++) by_color[i].clear();
    for(int i=1;i<=n;i++) {
        cin >> color[i];
        cnt[color[i]]++;
        sz[i] = 1; rep[i]=i;
        by_color[color[i]].push_back(i);
        v[i].clear();
        distinct.insert(color[i]);
    }
    for(int i=1;i<=n;i++){
        int col = color[i];
        if(cnt[col] == 1){
            q.push(col);
            mp[i].clear();
        }
    }
    for(int i=1;i<=m;i++){
        int a,b; cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
        if(color[a] == color[b]) Union(a,b);
    }
    while(!q.empty()){
        int f = q.front();
        q.pop();
        distinct.erase(f);
        vector<int> to_sort;
        int root=0;
        for(int c: by_color[f]){
            used[c] = true;
            if(!root) root = Find(c);
            for(int nbr: v[c]){
                if(!used[nbr]) to_sort.push_back(Find(nbr));
            }
        }
        sort(to_sort.begin(),to_sort.end(),[&](int a, int b){return color[a] < color[b];});
        for(int i=0;i<to_sort.size();i++){
            if(i && color[to_sort[i]] == color[to_sort[i-1]]) Union(to_sort[i],to_sort[i-1]);
            mp[root][color[to_sort[i]]] = Find(to_sort[i]);
        }
        for(int c: by_color[f]){
            for(int nbr: v[c]){
                if(used[nbr]) Union(c,nbr);
            }
        }
    }
    cout << (distinct.empty()? "TAK\n": "NIE\n");
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--) solve();
}