#include<stdio.h>#include<algorithm>#include<string.h>#include<iostream>using namespace std;const int N=10000;int head[N],dist[N],nc,_nc,_head[N];struct Edge{ int to,next;} edge[N*100],_edge[N*100];void add(int a,int b){ edge[nc].to=b; edge[nc].next=head[a]; head[a]=nc++;}void addf(int a,int b){ _edge[_nc].to=b; _edge[_nc].next=_head[a]; _head[a]=_nc++;}bool vis[N];int T;void diji(int n){ memset(dist,-1,sizeof(dist)); dist[T]=0; memset(vis,false,sizeof(vis)); for(int i=0;i<n;i++) { int k=-1,mmin=1<<30; for(int j=0;j<n;j++) if(!vis[j]&&dist[j]!=-1&&mmin>dist[j]) mmin=dist[k=j]; if(k==-1) return; vis[k]=true; for(int j=_head[k];j!=-1;j=_edge[j].next) { int t=_edge[j].to; if(dist[t]==-1||dist[t]>dist[k]+1) dist[t]=dist[k]+1; } }}bool check(int now){ vis[now]=true; if(now==T) return true; for(int i=head[now];i!=-1;i=edge[i].next) { if(!vis[edge[i].to]) { if(check(edge[i].to)) return true; } } return false;}int main(){ int n,a,b; scanf("%d%d",&n,&T); memset(head,-1,sizeof(head)); memset(_head,-1,sizeof(_head)); nc=_nc=0; while(scanf("%d%d",&a,&b)!=EOF) add(a,b),addf(b,a); diji(n); int ans=0; for(int i=1; i<n; i++) { if(i!=T&&dist[i]!=-1&&dist[i]<dist[ans]) { memset(vis,false,sizeof(vis)); vis[i]=true; if(!check(0)) ans=i; } } printf("Put guards in room %d.n",ans); return 0;}
