/*
                                                                                          
 =-@%+-=+=+.#%-=**-==++============+===++==========-==#=.-.:@#++*+===----=---==--=------- 
 =:%+=%**++**%.-*+-++===============================+*#.-:.*@**#*+==------==------------- 
 ===@+:-#-%+*+-=*+-==================++==============+@ -..@#++*+=++=-----==------==----- 
 ==:-@#:#%=+=:==*+-========+======--::.:--=---::::.: :#.:..@****+==+=------=------------= 
 =##:.***-.:-#:=*+-========---::.:+*#%@###%%%%@%%%%@@@#   +@****+====-------------------- 
 -**#*#+*%*+%%.=*+-==-====-: :+#@@#+**#%%%***++=+++=+#@@@:+#***+++=-------=-------------- 
 -=@=++*+-*#+@:=*+-=====-.:+@@%#++#*+*-....:-==++++##@@@@@@---++++=-------=--=----------- 
 *:@#=*=+*%+*=-=*+====---*@@%#+=*+--=*#@@@@@@@@@@@@@@@@@@@@@@*-::===--------=--=--------- 
 -:.%#*-%@-*=.=+++=+=--#%*=-=*#%@@@@@@#*++=----==--++*#%%%#%%@@@= -------=--------------- 
 :@=. *#+..:-%-=++--:=#+-+@@@@@%*+----=+++=++++++++++*+#*+#@%@@@@*.------=-=------=------ 
 .@#*+%-*%=#%@:+*-..#%-+%@@%*===+++++++***++++*++++++++=*###@##%%#-.--=--=-=------==----= 
 :#+=*-*++#*%:-++::@@#*@@@#+++***++++++*+++=+++++++++++++*###*-%*@# :----=-=------------- 
 -:@+--*=#**%:=*+.*@%**@@#++*+*+++++++++++++++++++++++*+++*+#**%+%*..--=----------------= 
 =-:%*:+%#*%-:=*=-@@*=#@#**+*+++==+++++=+++===+==+=+++++++***%%**%@* :---=--------------= 
 :#.:++#=:::*+=#=:@@+#@##+++++*+++==+++=========+++++++++****+#%#*%%..------------------= 
 :@+=#=*+%=@@+=%-:@@##%*##*++++***+=====+==++++++++++++++****+##**%@# :-----=------------ 
 .@=+=+*-+%%@.=%--@%@%###****+=====+==+++++++++=+===+++**#**++*###*@@. ..--=---------=--= 
 :*#=+-*+%=#%-=#--@%+*%*#****++++++++=+==++===+=++++++++**+*###*+%%#=.+-  :----------=--= 
 -:*%+.#@-@*--+#==@#%###*+**#**+++=++==+=++++++=*+=----==**+++*##**%@@@@@+.-==----------= 
 +-.-**#.--.*-== :@#***##***+=--===+===========-+:.:-==-:=++++#%##%@@%+*@+.-----=-==----- 
 @@=*%:+%==@@.=@@%%*###%***--..:....:.::=++=--.   *@@@@@@@#+**##+*#*--*#@+.-------==----= 
 *#-*-*+:*#@#.+@@@@#**%@***@@@@@@@@#+=+++++**+*@@@@%-.-*%@@****#*=%@#+##@-.--------=----= 
 :@=-++=*#-@:--***=%%*#@#*%@@*-   +@@@@@*=+#@@@@::     -:=###**##+#%#*#@+ :-------==----= 
 =-@*.*##:@==+++*#+=#+=%*=*#=-=%@@@@@@@@#=++##@@@@@@@@@@@%#==+**%#=:#*+@=.--------==----- 
 =. #*##:+::=-++=@#%@@**##*@@@@=@@. :. %@-:-+# ::.   -:-::#=+***%#=**+@@-.-----===------= 
 +=@# +.%#=+=-*+:@*=+*@@*+++..:. .:+%%#*%-:-%#=@@%*+-=+#**+=+=*##****%@+.:-----======---= 
 =::*-@%%--===%*.#@===*@*+++**@@@@@@===+@===%*-=:-@@@@@%+==+*+##*#%==+@+ --------===----- 
 :.=@@+.-=++=+##:=%%%#*%#*#*=----:::=++#%+::%#+**-. ..::-+****#***#*=+%-.-=--==--===---== 
 *%@@.-=++==+#*+=+*#+=+@#**##*====+=+***#+==*%*==--==-===++++****#*+%@*.-----========---- 
 @@-:-+++-=+##+-==+*+-+@#*++=====-=:=#%%*=+++*%#%*-:-===-=+*#**##@@@@. :-=-------===--:-: 
  =:=++++=+#*+=-===#%=+%#***+==-::+**==*=.:::=#=*%@%#====+*******@-  .---=------====---. :
 =++*++--**@-+*##*****@@%##*+=+=%@@@@%++-.. .-+.+@=#@%+********##@# -------=======-=--. @%
 +=--=+##@+--++**++*+:+@######%@@#==+#@@@@@@@@@@@#=-#@#*++*****##@# -==---====-======. @@*
 =*++*@%---====+***+++=#@*%@*+#@#**++===+#@@%*+-++++=+###*+*#***%@* --------=-====--: @@@+
 @@#*=-:==+++=+++**+++=@@**#*+##+====---:-+*+==-=+++=-=*#*+*#**#@-  -==--=--====++=. %@%%+
 -::-===+=++++++++****==%@##*=+##@@@@@@@#.     --+%@@###*++*#**%%@#   ---=----=+==. @@#%@+
 +++++++++++++++++****+=#@@#%+-=##*+**#@@@@@@@@@@@@#@@#+==+#**%@*#@@   :---=--==-. @@=#%%+
 =====+=====++++++*****+--####=++=-+%*=:        .:+--:++=+%#+%@@- #@@@   -==--=+: @@*+##%+
 ========++++++++++****+:.@@%@@++*++*@@@@@@@@@@@@@+-=+*#%%%*%%@#:==@@@@@  .==--: @@@*=*%@+
 +==++==+++*++++=+**+:.  @@-@@%#*+*#*+#@%#%%%%%*++*****+**+#@@#:=:.#@@@@@=  .-. @@%%#**%@ 
 =====++*++++**=     #@@@@# .@@@%+-====::------++==+===%@+@@@%-== -@@@%%@@@:   @@@%%#+%@@ 
 =+=++*+++=:    .@@@@@@@@@#...@@@@#===++++==+==------#@#%@@@.:--. *@@@@@%@@@@@@###+#%#@*  
 =++=-:.   +@@@@@@@@%%@@@@*.:..*@@@@*==--==+=-:+-==*@%%@@@=.-==- :@@@@@@@@@@@@@@@##:=*. . 
 -    +=@@@@@@@@@@@%%@@@@@%===- .@@@@@%##*+**+*#@@@@@@@%..-=*=-  #@@@@@@@@@@@@@@@@@@@*    
 ..@@@@@@@@@@@@@@%%@@@@@@@@%*#*=- .@@@@@@@@@@@@@@@@@@- :==+++=. *@@%@@@@@@@@@@@@@@@@@@@@@ 
@@@@@@@@@@@@@@%%%@@@@@@@@@*###*+--:. #@@+%@##@@@@= :.:++++++=: -@@@@@@@@@@@@@@@@@@@@@@@@@@
#@@@@@@@@@@@@@@@@@@@@@@@@%-+++##+==+.  .:=+@-. ..:-+++=====-: :@@%%@@@%@@@@@@@@@@@@%@@@@@*
#@@@@@@@@@@@@@@@@@@@@@@@@%:+==***+-  @#@@@@@%@   +-+=======- .@@@@@@@@@@@@@@@@%%%%%@@@@@@*
#@@@@@@@@@@@@@@@@@@@@@@@@#.---++*=.+@@@@%.*@@@@@  --==-----  @@@@@%@@@@@@@@@@@@@@@@@@%@@@*
#@@@@@@@@@@@@@@@@@@@@@@@@%:--==++.@@#@=@@@@* @@@@@ .-==-=-. #@@@@@@@@@@@@@@@@@@@%%%@@@@@@*
#@@@@@@@@@@@@@@@@@@@@@@@@#:---===%@#.@@@=.@@@@@ .%@% :===: =@@@%@@@@@@@@@@@@%%%%%@@@@%@@@*
#@@@@@@@@@@@@@@@@@@@@@@@@@=----+@%:  -@@%@@@@   ::-%@+-::  @@@%@@@@@@@@@@@@@@@@@@@@@@@@@@#
#@@@@@@@@@@@@@@@@@@@@@@@@@=.-=%*-:+* @@@*@@*  :---=::-%=  @@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@*
#@@@@@@@@@@@@@@@@@@@@@@@@@==+::--==+ =@@@#@  +:++==---:  @@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@*
#@@@@@@@@@@@@@@@@@@@@@@@@@+:=====--: @: %@@@ +:=----=-. @@@%%%@%@@@@@@@@@@@@@@@@@%%%@@@@@*
#@@@@@@@@@@@@@@@@@@@@@@@@@*.++=====  @@@@@@@  ====-==. =@@%@@@@@@@@@@@@@@@@@%@@@@@@@@@%@@*
#@@@@@@@@@@@@@@@@@@@@@@@@@+ ===--=. @@@@%:@@@ :===-=-  @@@%@@@@@@@@@@@@@@@%%@@@@@@@@@@@@%*
#@@@@@@@@@@@@@@@@@@@@@@@@@+ -====- @@% %@@@:@ .--=--  @@@%@@@@@@@@@@@@@@@@@@@@@%%@@@@@@@@*
#@@@@@@@@@@@@@@@@@@@@@@@@@* :-=++  @@@@@+%@+@+ ===-  @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*
#@@@@@@@@@@@@@@@@@@@@@@@@@@..---: @@@@@@ *@@@@ =-=. @@@@@%@@@@@@@@@@@%%%@@@@@@@@@@@@@@@@@*
#@@@@@@@@@@@@@@@@@@@@@@@@@@+.:-- #@@@  @@@=.@@ -=- -@@%@@@@@@@@@@@@@@%@@@@%@@@@@@@@@@@@@@*
#@@@@@@@@@@@@@@@@@@@@@@@@@@*:+=  @@-@@@@.@@@@@  -  @@@@@@@@@@%@@@@@@%%@@@@%@@@@@@@@@@@@@@*
#@@@@@@@@@@@@@@@@@@@@@@@@@@= +- @@@*@@@@:@@@%=:.. @@@@@@@%@@@@@@@@@%%@@@%@@@@@@@@@@@@@@@@*
#@@@@@@@@@@@@@@@@@@@@@@@@@@: =. @@@@@ =@@@ +@@@  @@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@*
#@@@@@@@@@@@@@@@@@@@@@@@@@@* . @@@=*@@@*@@#@@@# @@@@@@@@@@@%@@@%%@@@@@%@@@@@@@@@@@@@@@@@@*
#@@@@@@@@@@@@@@@@@@@@@@@@@@@.  @@@+%@@@.-@@@:%- @@@%@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@*
#@@@@@@@@@@@@@@@@@@@@@@@@@@@= @@=@@@. @@@* @@@#@@@@@@@@@@@@@@%@@@@%%@@@@@@@@@@@@@@@@@@@@@*
#@@@@@@@@@@@@@@@@@@@@@@@@@@@. @@@@+@@@@+@@@@%@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%*
#@@@@@@@@@@@@@@%@@@@@@@@@@@@ .@@@%*@%@@ @@@@ @%@@@@@@@@@@@@@@@@%%@@@@@@@@@@@@@@@@@@@@@@@@*
#@@@@@@@@@@@@@@@@@@@@@@@@@@@-@@ *@@* *@@@  @@@%@@@@@@@@@@@%%%@@@@@@@@@@@@@@@@@@@@@@@%%%@@*
#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@=@@@@@@@@@@@%%@@@@@@@@%@@@@@@@%@@@@@@@@@@@@@@@%%%%@@@@@@#
#@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@-#@@@.+@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@%@@@@@%@@@@@#
*###########***##*##########*@+ +%#  *##- %************#*********************#**######%##*
*/




#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define sz(a) (int)a.size()
#define pb push_back
#define st first
#define nd second
#define endl '\n'
#define fast ios_base::sync_with_stdio(NULL);cin.tie(0); cout.tie(0)
#define debug(x) cout << #x << " = " << x << endl;
#define vc vector
#define pii pair<int,int> 
#define pll pair<ll,ll> 

struct customhsh
{
    static ull splitmix(ull x)
    {
        x+=21372137ull;
        x+=(x^(x>>30))*67676767ull;
        x=(x^(x>>27))*67676969ull;
        return x^(x>>31);
    }

    size_t operator()(ull x)const
    {
        static const ull fixed=chrono::steady_clock::now().time_since_epoch().count();
        return splitmix(x+fixed);
    }

};
void solve()
{
    int n,m,k;
    cin >> n >> m >> k;

    vc<int> a(n);
    for(int i=0; i<n; ++i)
    {
        cin >> a[i];
        --a[i];
    }

    vc<vc<int>> g(n);
    vc<pii> e;

    for(int i=0; i<m; ++i)
    {
        int u,v;
        cin >> u >> v;
        --u;
        --v;
        g[u].pb(v);
        g[v].pb(u);
        e.pb({u,v});
    }

    vc<int> cid(n,-1);
    vc<int> ccol;
    vc<vc<int>> colnodes(k);
    vc<int> sot;
    int comps=0;

    for(int i=0; i<n; ++i)
    {
        if(cid[i]==-1)
        {
            int c=a[i];
            cid[i]=comps;
            sot.clear();
            sot.pb(i);
            while(!sot.empty())
            {
                int v=sot.back();
                sot.pop_back();
                for(int x:g[v])
                {
                    if(cid[x]==-1 and a[x]==c)
                    {
                        cid[x]=comps;
                        sot.pb(x);
                    }
                }
            }
            ccol.pb(c);
            colnodes[c].pb(comps);
            comps++;
        }
    }

    vc<vc<int>> cadj(comps);
    for(auto [u,v]:e)
    {
        int x=cid[u];
        int y=cid[v];
        if(x==y)
            continue;

        cadj[x].pb(y);
        cadj[y].pb(x);
    }

    vc<int> cnt(k,0);
    vc<bool> actcol(k,0);

    int need=0;
    for(int c=0; c<k; ++c)
    {
        if(!colnodes[c].empty())
        {
            cnt[c]=sz(colnodes[c]);
            need++;
        }
    }

    vc<int> lpar(comps);
    vc<int> lsz(comps,1);
    iota(all(lpar),0);

    auto lfind=[&](int x)
    {
        while(lpar[x]!=x)
        {
            lpar[x]=lpar[lpar[x]];
            x=lpar[x];
        }
        return x;
    };

    auto lunion=[&](int x, int y, int c)
    {
        x=lfind(x);
        y=lfind(y);
        if(x==y)
            return 0;
        
        if(lsz[x]<lsz[y])
            swap(x,y);
        
        lpar[y]=x;
        lsz[x]+=lsz[y];
        cnt[c]--;
        return 1;
    };

    vc<int> gpar(comps);
    vc<int> gsz(comps,1);
    iota(all(gpar),0);
    vc<unordered_map<int,int,customhsh>> mp(comps);
    deque<int> q;

    auto gfind=[&](int x)
    {
        while(gpar[x]!=x)
        {
            gpar[x]=gpar[gpar[x]];
            x=gpar[x];
        }
        return x;
    };

    auto tpush=[&](int c)
    {
        if(!actcol[c] and cnt[c]==1)
            q.pb(c);
    };

    auto gunion=[&](int x, int y)
    {
        x=gfind(x);
        y=gfind(y);
        if(x==y)
            return;

        if(sz(mp[x])<sz(mp[y]))
            swap(x,y);

        gpar[y]=x;
        gsz[x]+=gsz[y];

        for(auto &f:mp[y])
        {
            int c=f.st;
            if(actcol[c])
                continue;

            int rep=lfind(f.nd);
            auto it=mp[x].find(c);
            if(it==mp[x].end())
                mp[x][c]=rep;
            else
            {
                if(lunion(it->nd,rep,c))
                    tpush(c);
                it->nd=lfind(it->nd);
            }
        }

        mp[y].clear();
    };


    for(int c=0; c<k; ++c)
        if(cnt[c]==1)
            q.pb(c);

    int done=0;

    while(!q.empty())
    {
        int c=q.front();
        q.pop_front();
        if(actcol[c] or cnt[c]!=1)
            continue;

        actcol[c]=1;
        done++;

        for(int u:colnodes[c])
        {
            gpar[u]=u;
            gsz[u]=1;
            mp[u].clear();

            for(int v:cadj[u])
            {
                int cc=ccol[v];
                if(actcol[cc])
                    continue;

                int rep=lfind(v);
                auto it=mp[u].find(cc);
                if(it==mp[u].end())
                    mp[u][cc]=rep;
                else
                {
                    if(lunion(it->nd,rep,cc))
                        tpush(cc);
                    it->nd=lfind(it->nd);
                }
            }
            for(int v:cadj[u])
            {
                if(actcol[ccol[v]])
                    gunion(u,v);
            }
        }
    }

    cout << (done==need? "TAK":"NIE") << endl;
}

int main() 
{
    fast;
    int t=1;
    cin >> t;
    while(t--) 
        solve();
    return 0;
}