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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
#include <bits/stdc++.h>
using namespace std;
int p1[100067],roz[100067];
int p2[100067];
int find(int i) 
{
    if (p1[i]==i) return i;
    return p1[i]=find(p1[i]);
}

bool unionn(int i,int j) 
{
    int a=find(i);
    int b=find(j);
    if (a!=b) 
    {
        if (roz[a]<roz[b])
        {
            swap(a,b);
        }
        p1[b]=a;
        roz[a]+=roz[b];
        return true;
    }
    return false;
}
int find1(int i) 
{
    if (p2[i]==i) return i;
    return p2[i]=find1(p2[i]);
}
int main() 
{
    ios_base::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+1);
        for (int i=1; i<=n; i++)
        {
            cin>>a[i];
        }

        vector<vector<int>> adj(n+1,vector<int>(0));
        for (int i=0; i<m; i++) 
        {
            int u,v;
            cin>>u>>v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        vector<int> numer(n+1,-1);
        vector<int> col;
        int n1=0;

        for (int i=1; i<=n; i++) {
            if (numer[i]==-1) 
            {
                col.push_back(a[i]);
                int id=n1++;
                queue<int> q;
                q.push(i);
                numer[i]=id;
                while (!q.empty()) 
                {
                    int u=q.front(); q.pop();
                    for (int v:adj[u]) 
                    {
                        if (a[v]==a[i]&&numer[v]==-1) 
                        {
                            numer[v]=id;
                            q.push(v);
                        }
                    }
                }
            }
        }
        vector<vector<int>> adj2(n1);
        for (int u=1; u<=n; u++) 
        {
            for (int v:adj[u]) 
            {
                if (numer[u]!=numer[v]) 
                {
                    adj2[numer[u]].push_back(numer[v]);
                }
            }
        }

        for (int i=0; i<n1; i++) 
        {
            p1[i]=i;
            roz[i]=1;
            p2[i]=i;
            sort(adj2[i].begin(), adj2[i].end());
            adj2[i].erase(unique(adj2[i].begin(), adj2[i].end()), adj2[i].end());
        }
        vector<int> cnt(k+1,0);
        vector<vector<int>> c2(k+1);
        for (int i=0; i<n1; i++) 
        {
            cnt[col[i]]++;
            c2[col[i]].push_back(i);
        }
        queue<int> q;
        for (int i=1; i<=k; i++) 
        {
            if (cnt[i]<=1)
            {
                 q.push(i);
            }
        }
        vector<bool> git1(k+1,false);
        vector<bool> git2(n1,false);
        vector<map<int,int>> adj3(n1);
        while (!q.empty()) 
        {
            int c=q.front();
            q.pop();
            git1[c]=true;
            for (int i:c2[c]) 
            {
                git2[i]=true;
                for (int j:adj2[i]) 
                {
                    if (git2[j]) 
                    {
                        int u=find1(i);
                        int v=find1(j);
                        if (u!=v) 
                        {
                            if (adj3[u].size()<adj3[v].size())
                            {
                                swap(u,v);
                            }
                            for (auto [a,b]:adj3[v]) 
                            {
                                if (adj3[u].count(a)) 
                                {
                                    if (unionn(adj3[u][a],b)) 
                                    {
                                        cnt[a]--;
                                        if (cnt[a]==1)
                                        {
                                            q.push(a);
                                        }
                                    }
                                } 
                                else
                                {
                                    adj3[u][a]=b;
                                }
                            }
                            adj3[v].clear();
                            p2[v]=u;
                        }
                    } else {
                        int a=col[j];
                        int b=find1(i);
                        if (adj3[b].count(a)) 
                        {
                            if (unionn(adj3[b][a], j)) 
                            {
                                cnt[a]--;
                                if (cnt[a]==1)
                                {
                                    q.push(a);
                                }
                            }
                        } 
                        else 
                        {
                            adj3[b][a]=j;
                        }
                    }
                }
            }
        }
        bool wybuchlo=true;
        for (int i=1; i<=k; i++)
        { 
            if (!git1[i])
            {
             wybuchlo=false;
            }
        }
        if(wybuchlo)
        {
            cout<<"TAK"<<"\n";
        }
        else
        {
            cout<<"NIE"<<"\n";
        }
    }
}