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 un unsigned
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define per(i, a, b) for(ll i = a; i >= b; i--)
#define all(v) begin(v), end(v)
#define st first
#define nd second
using namespace std;
using ll = long long;
using bigi = __int128;
using pii = pair<ll, ll>;
const ll N = 1e5 + 5;
vector<int> G[N];
int kol[N];
int kap[N];
map<int, int> kapm[N];
int kan[N];
bool byl[N];
vector<int> wszyk[N];
void init(int n, int k){
    rep(i, 0, max(n, k) + 1){
        G[i].clear();
        kap[i] = i;
        wszyk[i].clear();
        byl[i] = 0;
        kan[i] = 0;
        kapm[i].clear();
    }
}
int Find(int x){
    if(kap[x] != x) kap[x] = Find(kap[x]);
    return kap[x];
}
void Union(int x, int y){
    x = Find(x); y = Find(y);
    if(x == y) return;
    if(kapm[x].size() > kapm[y].size()) swap(x, y);
    // cout << "Union " << x << ' ' << y << '\n';
    kap[x] = y;
    for(auto [i, j] : kapm[x]){
        if(j > 0) kapm[y][i] += j;
    }
}
bool check(int n, int k, int ilekol){
    queue<int> q;
    rep(i, 1, n + 1){
        if(!byl[kol[i]] && kapm[Find(i)][kol[i]] == wszyk[kol[i]].size()){
            byl[kol[i]] = true;
            q.push(kol[i]);
        }
    }
    rep(_, 0, ilekol){
        if(q.empty()) return false;
        auto ko = q.front();
        q.pop();
        // cout << ko << '\n';
        for(auto i : wszyk[ko]){
            for(auto j : G[i]){
                Union(i, j);
                if(!byl[kol[j]] && kapm[Find(j)][kol[j]] == wszyk[kol[j]].size()){
                    byl[kol[j]] = true;
                    q.push(kol[j]);
                }
            }
        }
    }
    // rep(i, 1, k + 1){
    //     cout << kan[i] << ' ';
    // }
    // cout << '\n';
    return true;
}
void solve(){
    int n, m, k;
    cin >> n >> m >> k;
    init(n, k);
    rep(i, 1, n + 1){
        cin >> kol[i];
        kapm[i][kol[i]] = 1;
        wszyk[kol[i]].push_back(i);
    }
    rep(i, 0, m){
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    rep(i, 1, n + 1){
        for(auto j : G[i]){
            if(kol[i] == kol[j]) Union(i, j);
        }
    }
    int ilekol = 0;
    rep(i, 0, k + 1){
        if(!wszyk[i].empty()) ilekol++;
    }
    if(check(n, k, ilekol)){
        cout << "TAK\n";
    }
    else{
        // rep(i, 1, k + 1) cout << kan[i] << '\n';
        cout << "NIE\n";
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}