#include <iostream>
#include <list>
using namespace std;

bool dfs(int v, list<int>* graph, int * visited, bool & DRAW, list <int> & win_result)
{
    // VISITED:
    //0 - nieodwiedzony
    //1 - odwiedzony w obecnym wywolaniu
    //2 - odwiedzony w poprzednim wywolaniu

    visited[v]=1;
    win_result.push_back(v/2);
    if (graph[v].empty() && v%2==0) //brak sasiadow i zielony wierzcholek
        return true;

    for (int u: graph[v])
        if (visited[u]==1) //cykl
            DRAW=true;
        else
            if (visited[u]==0 && dfs(u,graph,visited,DRAW,win_result))
                return true;

    visited[v]=2;
    win_result.pop_back();
    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    int t,n,m,x,y,s;
    bool DRAW;
    list<int> * graph;
    int * visited;
    list <int> win_result;

    cin >> t;
    for (int i=0;i<t;i++)
    {
        win_result.clear();
        DRAW=false;
        cin >> n >> m >> s;

        graph=new list<int>[2*n]; // zielony wierzcholek i jest pod indeksem 2*i, czerwony pod indeksem 2*i+1
        visited=new int[2*n];
        for (int j=0;j<2*n;j++)
            visited[j]=0;

        for (int j=0;j<m;j++)
        {
            cin >> x >> y;
            graph[2*x].push_back(2*y+1); // zielony x -> czerwonego y
            graph[2*x+1].push_back(2*y); // czerwony x -> zielony y
        }

        if (dfs(2*s,graph,visited,DRAW,win_result)) // zaczynam od zielonego s
        {
            cout << "TAK" << endl;
            for (int k: win_result)
                cout << k <<" ";
            cout << endl;
        }
        else
            if (DRAW)
                cout << "REMIS" << endl;
            else
                cout << "NIE" << endl;
    }
}