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

#define ll long long
#define s second
#define f first

const int N=1e5+100;
vector <int> graf[N], kolor[N];
int uf[N], ile[N], co[N];
set <int> rzecz[N];
bool vis[N];
queue <int> kol;

int finde( int x ){
    if( uf[x] == x )
        return x;
    uf[x] = finde(uf[x]);
    return uf[x];
}

void uni( int x, int y ){
    x = finde(x); y=finde(y);
    // cerr << "INSIDE " << x << ' ' << y << '\n';
    if( x == y )    
        return;
    if( rzecz[x].size() < rzecz[y].size() )
        swap( x, y );
    uf[y]=x;
    for( auto it = rzecz[y].begin(); it != rzecz[y].end() ; ++it ){
        // cerr << "JESTEM " << y << ' ' << *it << '\n';
        if( rzecz[x].count(*it) ){
            // cerr << "DELETE " << *it << ' ' << ile[*it] << '\n';
            ile[ *it ]--;
            if( ile[*it] <= 1 && !vis[*it] ){
                vis[*it]=1;
                kol.push(*it);
            }
        }
        else{
            rzecz[x].insert(*it);
        }
    }
    return;
}

void rozw(){
    while( !kol.empty() ){
        int u = kol.front();
        kol.pop();
        for( int i:kolor[u] )
            for( int j:graf[i] )
                uni(i,j);
        kolor[u].clear();
    }
    return;
}

void solve(){
    int ilewar, ilepol, pol1, pol2, war, ilekol;
    cin >> ilewar >> ilepol >> ilekol;
    for( int i=0; i<ilewar; ++i ){
        cin >> war;
        co[i+1]=war;
        kolor[war].push_back(i+1);
        ile[war]++;
        uf[i+1]=i+1;
        rzecz[i+1].clear();
        rzecz[i+1].insert(war);
        graf[i+1].clear();
    }
    while( !kol.empty() )
        kol.pop();
    for( int i=0; i<ilepol; ++i ){
        cin >> pol1 >> pol2;
        if( co[pol1] != co[pol2] ){
            graf[pol1].push_back( pol2 );
            graf[pol2].push_back( pol1 );
        }
        else{
            uni( pol1, pol2 );
        }
    }
    for( int i=1; i<=ilekol; ++i ){
        if( !vis[i] && ile[i] <= 1 )
            kol.push(i);
    }
    rozw();
    bool odp=1;
    for( int i=0; i<=ilekol; ++i ){
        if( ile[i] > 1 && kolor[i].size()){
            odp = 0;
            // cerr << i << ' ' << ile[i] << ' ' << kol.size() << '\n';
        }
        // if( ist.count(i) && ile[i] < 1 )
            // cerr << i << ' ' << ile[i] << ' ' << kol.size() << '\n';
        kolor[i].clear();
        ile[i]=0;
        vis[i]=0;
    }
    if( odp )
        cout << "TAK\n";
    else
        cout << "NIE\n";
    return ;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int ilete;
    cin >> ilete;
    for( int i=0; i<ilete; ++i ){
        solve();
    }
    
    return 0;
}