#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;
bool win=false;
bool remis=false;
bool remis2=false;
struct wezel
{
    int i;
    vector <int> sasiedzi;
    bool czer=0;
    bool ziel=0;
    int drogaczer;
    int drogaziel;
};
void bfs(queue<int> &qg, queue<int>&qr,int i, wezel tab[])
{
    int wsk;
while(qg.size()!=0 || qr.size()!=0)
{
    if(qg.size()!=0)
    {

        while(qg.size()!=0)
        {

            wsk=qg.front();
            qg.pop();
            vector<int>::iterator it;
            int wskk;
            if(tab[wsk].sasiedzi.size()==0&& tab[wsk].ziel==true)
            {
                cout << "TAK"<< "\n";
                win=true;
                stack<int> s;
                while(i!=0)
                {
                    if(i==0)
                        break;
                    s.push(wsk);
                    wsk=tab[wsk].drogaczer;
                    i--;
                    if(i==0)
                        break;
                    s.push(wsk);
                    wsk=tab[wsk].drogaziel;
                    i--;
                }
                while(s.size()!=0)
                {
                    cout<<s.top() << " ";
                    s.pop();
                }
              cout<<"\n";
                return;
            }
            else if(tab[wsk].sasiedzi.size()!=0)
            {
                sort(tab[wsk].sasiedzi.begin(), tab[wsk].sasiedzi.end());
                remis2=true;
                for(it=tab[wsk].sasiedzi.begin(); it!=tab[wsk].sasiedzi.end(); ++it)
                {

                    wskk=*it;
                    if(tab[wskk].czer && tab[wsk].ziel)
                    {
                        remis=true;
                    }
                    if(tab[wskk].czer==false && tab[wsk].ziel)
                    {
                        tab[wskk].czer=true;
                        tab[wskk].drogaziel=wsk;
                        qr.push(wskk);
                    }
                }
            }
        }
        i++;
    }
    else
    {
        while(qr.size()!=0)
        {

            wsk=qr.front();
            qr.pop();
            vector<int>::iterator it;
            int wskk;
            if(tab[wsk].sasiedzi.size()!=0)
            {
                sort(tab[wsk].sasiedzi.begin(), tab[wsk].sasiedzi.end());
                remis2=true;
                for(it=tab[wsk].sasiedzi.begin(); it!=tab[wsk].sasiedzi.end(); ++it)
                {
                    wskk=*it;
                    if(tab[wskk].ziel && tab[wsk].czer)
                    {
                        remis=true;
                    }

                    if(tab[wskk].ziel==false && tab[wsk].czer)
                    {

                        tab[wskk].ziel=true;
                        tab[wskk].drogaczer=wsk;
                        qg.push(wskk);
                    }
                }
            }

        }
        i++;
    }
}
}
int main()
{
    ios_base::sync_with_stdio(false);
    int p;
    cin >> p;
    for(int i =0; i<p; i++ )
    {
        int k;
        int m;
        int poz;
        cin >> k >> m >> poz;
        wezel tab[k];
       // wezel **tab= new wezel*[k];
        for(int b=0; b<k; b++)
        {
                        // to przekracza pamięć
              tab[b].i=b;
        }

        int a,b;
        for(int j=0; j<m; j++)
        {
            cin >> a >> b;
            tab[a].sasiedzi.push_back(b);
        }
        queue <int> qg;
        tab[poz].ziel=true;
        qg.push(poz);
        queue <int> qr;
        bfs(qg,qr,1,tab);
        if(!win && (remis || !remis2))
            cout << "REMIS"<<"\n";
        else if(!win)
            cout << "NIE"<< "\n";
        win=false;
        remis=false;
        remis2=false;
    }
}