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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <bits/stdc++.h>
using namespace std;

struct hh{
    static uint64_t sm(uint64_t x){
        x+=0x9e3779b97f4a7c15;
        x=(x^(x>>30))*0xbf58476d1ce4e5b9;
        x=(x^(x>>27))*0x94d049bb133111eb;
        return x^(x>>31);
    }
    size_t operator()(uint64_t x)const{
        static const uint64_t rd=chrono::steady_clock::now().time_since_epoch().count();
        return sm(x+rd);
    }
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin>>t;
    while(t--){
        int n,m,k;
        cin>>n>>m>>k;
        vector<int>a(n);
        for(int i=0;i<n;i++){
            cin>>a[i];
            --a[i];
        }

        vector<vector<int>> g(n);
        vector<pair<int,int>> ed;
        ed.reserve(m);
        for(int i=0,u,v;i<m;i++){
            cin>>u>>v;
            --u;--v;
            g[u].push_back(v);
            g[v].push_back(u);
            ed.push_back({u,v});
        }

        vector<int> id(n,-1),cl;
        vector<vector<int>> by(k);
        int q=0;
        for(int i=0;i<n;i++) if(id[i]<0){
            int c=a[i];
            vector<int> st={i};
            id[i]=q;
            for(int p=0;p<(int)st.size();p++){
                int x=st[p];
                for(int y:g[x]) if(id[y]<0&&a[y]==c){
                    id[y]=q;
                    st.push_back(y);
                }
            }
            cl.push_back(c);
            by[c].push_back(q);
            q++;
        }

        vector<vector<int>> h(q);
        for(auto [u,v]:ed){
            u=id[u];
            v=id[v];
            if(u!=v){
                h[u].push_back(v);
                h[v].push_back(u);
            }
        }

        vector<int> p1(q),p2(q),r2(q),ct(k);
        iota(p1.begin(),p1.end(),0);
        iota(p2.begin(),p2.end(),0);

        vector<char> on(q,0),ac(k,0);
        vector<unordered_map<int,int,hh>> mp(q);

        auto f1=[&](int x){
            while(p1[x]!=x){
                p1[x]=p1[p1[x]];
                x=p1[x];
            }
            return x;
        };
        auto f2=[&](int x){
            while(p2[x]!=x){
                p2[x]=p2[p2[x]];
                x=p2[x];
            }
            return x;
        };
        auto j2=[&](int x,int y){
            x=f2(x);
            y=f2(y);
            if(x==y) return pair<int,int>{x,0};
            if(r2[x]<r2[y]) swap(x,y);
            p2[y]=x;
            if(r2[x]==r2[y]) r2[x]++;
            ct[cl[x]]--;
            return pair<int,int>{x,1};
        };
        auto ad=[&](int r,int c,int v,queue<int>&qu){
            r=f1(r);
            v=f2(v);
            auto &d=mp[r];
            auto it=d.find(c);
            if(it==d.end()) d[c]=v;
            else{
                auto [z,b]=j2(it->second,v);
                it->second=f2(z);
                if(b&&ct[c]==1&&!ac[c]) qu.push(c);
            }
        };
        auto mg=[&](int x,int y,queue<int>&qu){
            x=f1(x);
            y=f1(y);
            if(x==y) return x;
            if(mp[x].size()<mp[y].size()) swap(x,y);
            p1[y]=x;
            for(auto &kv:mp[y]){
                int c=kv.first;
                if(ac[c]) continue;
                int v=f2(kv.second);
                auto it=mp[x].find(c);
                if(it==mp[x].end()) mp[x][c]=v;
                else{
                    auto [z,b]=j2(it->second,v);
                    it->second=f2(z);
                    if(b&&ct[c]==1&&!ac[c]) qu.push(c);
                }
            }
            unordered_map<int,int,hh>().swap(mp[y]);
            return x;
        };

        int all=0;
        queue<int> qu;
        for(int c=0;c<k;c++){
            ct[c]=(int)by[c].size();
            if(ct[c]){
                all++;
                if(ct[c]==1) qu.push(c);
            }
        }

        int ok=0;
        while(!qu.empty()){
            int c=qu.front();
            qu.pop();
            if(ac[c]||ct[c]!=1) continue;
            ac[c]=1;
            ok++;

            for(int u:by[c]) on[u]=1;

            for(int u:by[c]) for(int v:h[u]) if(on[v]) mg(u,v,qu);

            for(int u:by[c]){
                int r=f1(u);
                for(int v:h[u]) if(!on[v]&&!ac[cl[v]]) ad(r,cl[v],v,qu);
            }
        }

        cout<<(ok==all?"TAK\n":"NIE\n");
    }
    return 0;
}