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
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define RFOR(i,p,n) for(int i=(p);i>=(n);--i)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define ssize(x) int((x).size())
#define fi first
#define se second
#define V vector
#define pb push_back
#define eb emplace_back
#define C const
#define gc getchar_unlocked
#define pc putchar_unlocked
#define pn putchar_unlocked('\n')
using namespace std;
typedef long long ll;
typedef __int128_t lll;
typedef V<int> vi;
typedef V<ll> vll;
typedef const int ci;
typedef const ll cll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
void chmin(auto &a, auto b){a=min(a,b);}
void chmax(auto &a, auto b){a=max(a,b);}
ci inf = 2.1e9;
cll infll = 4.5e18;
int I(){
    int z;
    int c = gc();
    while(c < '0' || c > '9') c = gc();
    for(z = 0; c >= '0' && c <= '9'; c = gc()) z = 10*z+c-'0';
    return z;
}

void answer(){
    ci n = I();
    ci m = I();
    ci k = I();
    vi kol(n+1);
    V<vi> kub(k+1);
    FOR(i, 1, n) kol[i] = I(), kub[kol[i]].eb(i);
    V<vi> g(n+1);
    REP(_, m){
        ci a = I(), b = I();
        g[a].eb(b);
        g[b].eb(a);
    }

    vi usun(k+1, 0), wkolejce(k+1, 0);
    queue<int> q;
    auto dod = [&](ci kolor){
        if(wkolejce[kolor]) return;
        wkolejce[kolor] = 1;
        q.emplace(kolor);
    };
    FOR(i, 1, k) if(ssize(kub[i]) <= 1) dod(i);

    vi rep(n+1);
    FOR(i, 1, n) rep[i] = i;
    vi roz(n+1, 1);
    V<map<int, int>> mapy(n+1);
    auto f = [&](this auto &&ff, ci x) -> int{
        if(rep[x] == x) return x;
        return rep[x] = ff(rep[x]);
    };
    auto u = [&](int a, int b){
        a = f(a);
        b = f(b);
        if(a == b) return;
        roz[a] += roz[b];
        rep[b] = a;
        if(roz[a] == ssize(kub[kol[a]])) dod(kol[a]);
    };

    FOR(i, 1, n) for(int j : g[i]) if(kol[i] == kol[j]) u(i, j);

    while(ssize(q)){
        ci kolor = q.front();
        q.pop();
        usun[kolor] = 1;
        for(ci i : kub[kolor]) for(ci j : g[i]) if(!usun[kol[j]]){
            if(mapy[f(i)].contains(kol[j])) u(mapy[f(i)][kol[j]], j);
            else mapy[f(i)][kol[j]] = j;
        }
        for(ci i : kub[kolor]) for(ci j : g[i]) if(usun[kol[j]]){
            int ii = f(i);
            int jj = f(j);
            if(ii == jj) continue;
            if(ssize(mapy[jj]) > ssize(mapy[ii])) swap(ii, jj);
            for(auto [kk, tmp] : mapy[jj]) if(!usun[kk]){
                if(mapy[ii].contains(kk)) u(mapy[ii][kk], tmp);
                else mapy[ii][kk] = tmp;
            }
            rep[jj] = ii;
        }
    }

    FOR(i, 1, k) if(!usun[i]){
        pc('N'), pc('I'), pc('E'), pc('\n');
        return;
    }
    pc('T'), pc('A'), pc('K'), pc('\n');
}

int main(){
    int tt = I();
    while(tt--) answer();
}