#include <stdio.h>
#include <malloc.h>
int m,n;
int *iv,*ie,*in,*ic,*id;

void lookup(int idx,int idx_id)
{
   int i,j,k;
   if (idx==n)
   {
       for (i=0;i<idx_id ;++i )
       {
           in[id[i]]++;
           if (ic[id[i]] > idx_id-i)
           {
               ic[id[i]]=idx_id-i;
           }
       }
   }
   iv[idx]=1;
   id[idx_id]=idx;
   for (i=0;i<m ;++i )
   {
      if (ie[idx*m+i]==1 && iv[i]==0)
      {
          lookup(i,idx_id+1);
      }
   }
   iv[idx]=0;
}

int main()
{
   int i,j,k;
   scanf("%d %d",&m,&n);
   ie=(int *)malloc(m*m*sizeof(int));  
   iv=(int *)malloc(m*sizeof(int));  
   id=(int *)malloc(m*sizeof(int));  
   in=(int *)malloc(m*sizeof(int));  
   ic=(int *)malloc(m*sizeof(int));  
   for (i=0;i<m ;++i )
   {
      iv[i]=0;
      in[i]=0;
      id[i]=0;
      ic[i]=m;
      for (j=0;j<m ;++j )
      {
         ie[i*m+j]=0;
      }
   }
   while(scanf("%d %d",&i,&j)==2 && !(i==0 && j==0))
   {
      ie[i*m+j]=1;
   }

   lookup(0,0);

   j=m;
   for (i=0;i<m ;++i )
  {
      if (in[i]==in[0] && ic[i]<j)
      {
         k=i;
      }
   }
   printf("Put guards in room %d.\n",k);
   return 0;
}