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

 
#define ll long long
#define ve vector
#define fi first
#define se second
#define pb push_back
#define all(x) begin(x), end(x)
 
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll mod = 1e9+7, mod2 = 1e9+9;

struct dsu{
    ve<int> p;
    ve<set<int> > g;
    dsu(int n): p(n, -1), g(n) {}
    int findset(int a){
        if(p[a] < 0)
            return a;
        return p[a] = findset(p[a]);
    }
    void unionsets(int a, int b){
        a = findset(a);
        b = findset(b);
        if(a == b)
            return;
        if(g[a].size() < g[b].size())
            swap(a, b);
        p[b] = a;
        for(auto i : g[b])
            g[a].insert(i);
        g[b].clear();
    }
};

int ct = 1;

//72
void solve(){
    int n, m, k;
    cin >> n >> m >> k;
    // cout << ct++ << ":" << endl;
    // cout << n << " " << m << " " << k << endl;
    ve<int> a(n);
    ve<int> cnt(k, 0);
    for(auto& i : a){
        cin >> i;
        // cout << i << " ";
        i--;
        cnt[i]++;
    }
    // cout << endl;
    dsu d(n);
    queue<int> q;
    for(int i = 0; i < n; i++)
        if(cnt[a[i]] == 1)
            q.push(i);
    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        // cout << u << " " << v << endl;
        u--; v--;
        if(a[u] == a[v] && d.findset(u) != d.findset(v)){ 
            d.unionsets(u, v);
            cnt[a[u]]--;
            if(cnt[a[u]] == 1){
                q.push(u);
            }
        }
        else{
            d.g[d.findset(u)].insert(v);
            d.g[d.findset(v)].insert(u);
        }
    }
    ve<int> prv(k, -1);
    while(!q.empty()){
        int v = q.front();
        v = d.findset(v);
        // cout << v << endl;
        q.pop();
        ve<int> tomrg;
        for(auto to : d.g[v]){
            if(prv[a[to]] != -1 && d.findset(to) != d.findset(prv[a[to]])){
                d.unionsets(to, prv[a[to]]);
                cnt[a[to]]--;
                if(cnt[a[to]] == 1){
                    q.push(to);
                }
            }
            if(cnt[a[to]] == 1){
                tomrg.push_back(to);
            }
            prv[a[to]] = to;
        }
        for(auto i : tomrg)
            d.unionsets(v, i);
        for(auto to : d.g[v])
            prv[a[to]] = -1;
    }
    if(*max_element(all(cnt)) <= 1)
        cout << "TAK\n";
    else cout << "NIE\n";
}
 
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int T;
    cin >> T;
    while(T--){
        solve();
    }
}