记录编号	257283	评测结果	WWWWEEEEEE
题目名称	[焦作一中2012] 玻璃球游戏	最终得分	0
用户昵称	Respawn	是否通过	未通过
代码语言	C++	运行时间	0.442 s
提交时间	2016-05-02 11:22:01	内存使用	0.35 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=100;
int n,m,d,t=0;
void Dfs(int,int);
int a[maxn][maxn],deep[maxn],time1[maxn],time2[maxn];
bool f[maxn];
void Init();
int Find(int);
int main()
{
	freopen("marbles.in","r",stdin);
	freopen("marbles.out","w",stdout);
	Init();
	return 0;
}
void Init()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		a[x][y]=1;
	}
	Dfs(1,0);//cout<<"adkhdk";
	scanf("%d",&d);
	for(int i=1;i<=d;i++)
	{
		int mi=0x7f7f7f7f,p;
		int x,y;
		scanf("%d%d",&x,&y);
		for(int j=min(time1[x],time1[y]);j<=max(time1[x],time1[y]);j++)
		{
			if(mi>deep[time2[j]])
			{
				mi=deep[time2[j]];
				p=j;
			}
		}
		printf("%d",time2[p]);
	}
}
void Dfs(int x,int y)
{
	t++;
	if(f[x]==0)
	{
		f[x]=1;
		time1[x]=t;
		deep[x]=y+1;
	}
	time2[t]=x;
	for(int i=1;i<=n;i++)
	{
		if(a[x][i]>0)
		{
			Dfs(i,deep[x]);
			t++;
			time2[t]=x;
		}
	}
}
/*
7 6
1 2
1 4
2 3
2 5
4 6
4 7
10
*/