#include <stdio.h>

#include <string.h>

#include <queue>

using namespace std;

#define INF 0x3f3f3f3f

#define MAXN 105

int n,et;///n个房间，外星人所在的房间

bool data[MAXN][MAXN];   ///图的邻接矩阵

int dis[MAXN];           ///各点到外星人的房间的最短路径长度

int used[MAXN];

///广度优先搜索，站在外星人的角度看，就是单源最短路径问题

///搜索各个房间到外星人最短距离

void bfs_path()

{

    memset(dis,INF,sizeof(dis));

    dis[et]=;

    queue <int>q;

    q.push(et);

    int x;

    while(!q.empty())

    {

        x=q.front();    ///取队列头结点

        q.pop();

        for(int i=;i<n;i++)

        {

            ///经过房间x到外星人比从房间i到ET更近

            if(data[i][x]&&dis[x]+<dis[i])

            {

                q.push(i);

                dis[i]=dis[x]+;

            }

        }

    }

}

///去掉房间i,从房间0出发,判断能否到达外星人房间

///深度优先搜索

///形参id是当前正在搜索的房间编号

int dfs_search(int id)

{

    ///成功到达外星人房间

    if(id==et) return ;

    ///房间id已经搜索

    used[id]=;

    ///搜索下一个出口

    for(int i=;i<n;i++)

    {

        if(!used[i]&&data[id][i])

        {

            if(dfs_search(i)) return ;

        }

    }

    return ;

}

int main()

{

    int T,iCase;

    char line[];

    int a,b;///源房间，目标房间

    scanf("%d",&T);

    for(iCase=;iCase<T;iCase++)

    {

        scanf("%d%d\n",&n,&et);

        memset(data,false,sizeof(data));

        ///读取数据

        while(gets(line))

        {

            if(strcmp(line,"")==)

                break;

            sscanf(line,"%d%d",&a,&b);

            data[a][b]=true;

        }

        bfs_path();

        ///枚举搜索最优解

        int d=dis[];

        int room=;

        for(int i=;i<n;i++)

        {

            if(i==et) continue;

            memset(used,,sizeof(used));

            ///设置在房间i,也就是说在图中将房间i拿掉

            used[i]=;

            if(!dfs_search()&&dis[i]<d)

            {

                room=i;

                d=dis[i];

            }

        }

        if(iCase)    printf("\n");

        printf("Put guards in room %d.\n",room);

    }

    return ;

}