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;
using ll = long long;

vector < vector <ll> > graf;
vector <ll> d;
vector <ll> a;

ll bfs(ll x, ll y, ll z){
    ll s=1, i;
    queue <ll> k;
    k.push(x);
    d[x] = y;

    while (!k.empty()){
        x = k.front();
        k.pop();

        for (i=0; i<graf[x].size(); ++i){
            if (d[ graf[x][i] ] != y &&
            (a[ graf[x][i] ] == z || a[ graf[x][i] ] == 0)){
                d[ graf[x][i] ] = y;
                k.push( graf[x][i] );
                
                if (a[ graf[x][i] ] == z)
                    ++s;
            }
        }
    }
    
    return s;
}

void test(){
    ll n, m, k, u, v, lk, i, j, l;
    cin >> n >> m >> k;

    a = vector <ll>(n+1);
    vector < pair <ll, ll> > p(k+1, {0, 0});
    for (i=1; i<=n; ++i){
        cin >> a[i];
        ++p[a[i]].first;
        p[a[i]].second = i;
    }

    graf = vector < vector <ll> >(n+1);
    for (i=0; i<m; ++i){
        cin >> u >> v;
        
        graf[u].push_back(v);
        graf[v].push_back(u);
    }

    for (i=0; i<n; ++i){
        d = vector <ll>(n+1, 0);
        bool ok=false;
        
        for (j=1; j<=k; ++j){
            if (a[ p[j].second ] == 0)
                continue;
            
            if (bfs(p[j].second, j, j) == p[j].first){
                ok = true;
                lk = 0;
                for (l=1; l<=n; ++l){
                    if (a[l] == j)
                        a[l] = 0;
                    
                    if (a[l] == 0)
                        ++lk;
                }
                
                if (lk == n){
                    cout << "TAK\n";
                    return;
                }
                
                break;
            }
        }
        
        if (!ok){
            cout << "NIE\n";
            return;
        }
    }
    
    cout << "TAK\n";
}

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

    ll t, i;
    cin >> t;
    
    for (i=0; i<t; ++i)
        test();
    
    return 0;
}