先广搜建立最短路生成树，对于可以直接到达ET的点存下，然后求出这几个点在最短路生成树上的lca既为答案。。。
数据如此之水，为什么还是wa？？？

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int n,t;
struct Edge
{
	int id;
	int next;
}edge[10000];
Edge tree[10000];
int head[1000],top=0;;
int tree_head[1000];
void insert(int from,int to)
{
	edge[top].id=to;
	edge[top].next=head[from];
	head[from]=top;
	top++;
}
void insert2(int from,int to)
{
	tree[top].id=to;
	tree[top].next=tree_head[from];
	tree_head[from]=top;
	top++;
}
int query[100],q_cnt=0;
int queue[10000];
bool visit[1000];
void bfs()
{
	int i,j;
	memset(visit,0,sizeof(visit));
	top=0;
	queue[0]=0;
	visit[0]=1;
	int front=0,back=1,temp;
	while(front<back)
	{
		temp=queue[front++];
		for(i=head[temp];i!=-1;i=edge[i].next)
		{
			if(visit[edge[i].id])
				continue;
			else if(edge[i].id==t)
			{
				query[q_cnt++]=temp;
				continue;
			}
			visit[edge[i].id]=1;
			insert2(temp,edge[i].id);
			queue[back++]=edge[i].id;
		}
	}
}
int rmq[1000],rmq_cnt=0;
int deep[1000];
int pos[1000];
void dfs(int i,int d)
{
	visit[i]=1;
	rmq[++rmq_cnt]=i;
	deep[rmq_cnt]=d;
	if(pos[i]==0)
		pos[i]=rmq_cnt;
	for(int j=tree_head[i];j!=-1;j=tree[j].next)
	{
		if(!visit[tree[j].id])
		{
			dfs(tree[j].id,d+1);
			rmq[++rmq_cnt]=i;
			deep[rmq_cnt]=d;
		}
	}
}
int f[1000][100];
int min(int a,int b)
{
	if(a<b)
		return a;
	return b;
}
int tow[100];
int cal_rmq(int i,int j)
{
	int temp;
	if(i>j)
	{
		temp=i;
		i=j;
		j=temp;
	}
	int k=(int )sqrt((double)(j-i+1));
	//return min(f[i][k],f[j-tow[k]+1][k]);
	if(deep[f[i][k]]<deep[f[j-tow[k]+1][k]])
		return f[i][k];
	else
		return f[j-tow[k]+1][k];
}


int main()
{
	
	int i,j;
	int a,b;
	scanf("%d%d",&n,&t);
	memset(head,-1,sizeof(head));
	memset(tree_head,-1,sizeof(tree_head));
	while(scanf("%d%d",&a,&b)!=EOF)
		insert(a,b);
	bfs();
	//insert2(1,2),insert2(1,3),insert2(1,4),insert2(2,5),insert2(2,6);
	memset(visit,0,sizeof(visit));
	dfs(0,0);
	tow[0]=1;
	for(i=1;i<=30;i++)
		tow[i]=tow[i-1]*2;
	for(i=1;i<=rmq_cnt;i++)
		f[i][0]=i;
	for(i=rmq_cnt;i>=1;i--)
	{
		for(j=1;i+tow[j]-1<=rmq_cnt;j++)
		{
			//f[i][j]=min(deep[f[i][j-1]],deep[f[i+tow[j-1]][j-1]]);
			if(deep[f[i][j-1]]<deep[f[i+tow[j-1]][j-1]])
				f[i][j]=f[i][j-1];
			else
				f[i][j]=f[i+tow[j-1]][j-1];
		}
	}
	int temp=query[0];
	for(i=1;i<q_cnt;i++)
	{
		temp=rmq[cal_rmq(pos[temp],pos[query[i]])];
	}
	//printf("%d\n",rmq[cal_rmq(pos[1],pos[4])]);
	printf("Put guards in room %d.\n",temp);
}