hdu 2485

//점을 뜯어 가장자리를 만들고 하나의 그림을 구성하여 최대 흐름을 구한다. 먼저 두 번 bfs를 찾아서 각 점에서 1시와 n점의 최단로를 찾아낸다. 그리고 점을 뜯을 때 이 점에서 1시와 n점의 최단로의 합이 k보다 작으면 i에서 i+n까지의 유량을 1로 설정한다. 그렇지 않으면 0이고 그림에서 원래의 변의 유량은 inf이다. 마지막은 최대 흐름의 문제이다.
//이 문제는 최소 비용 흐름으로도 풀 수 있으며, 잠시 후에 코드를 보충합니다
//최대 스트림 코드:

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
#define inf 1000000
int bdis[55],hdis[55],vis[110];
int map[55][55],dis[55],n,cap[110][110];
void bfs(int start)
{
	int i;
	queue <int> que;
	for(i=1;i<=n;i++)
		dis[i]=inf;
	que.push(start);
	dis[start]=0;
	while(!que.empty())
	{
		int u=que.front();
		que.pop();
		for(i=1;i<=n;i++)
		{
			if(map[u][i]&&dis[u]+1<dis[i])
			{
				dis[i]=dis[u]+1;
				que.push(i);
			}
		}
	}
}

int pre[110];
int maxflow(int start,int end)
{
	int i,res=0,Min;
	while(1)
	{
		queue <int> que;
		memset(vis,0,sizeof(vis));
		que.push(start);
		vis[start]=1;
		while(!que.empty())
		{
			int u=que.front();
			que.pop();
			if(vis[end])break;
			for(i=start;i<=end;i++)
			{
				if(!vis[i]&&cap[u][i]>0)
				{
					vis[i]=1;
					pre[i]=u;
					que.push(i);
				}
			}
		}
		if(!vis[end])break;
		Min=inf;
		for(i=end;i!=start;i=pre[i])
		{
			if(cap[pre[i]][i]<Min)Min=cap[pre[i]][i];
		}
		res+=Min;
		for(i=end;i!=start;i=pre[i])
		{
			cap[pre[i]][i]-=Min;
			cap[i][pre[i]]+=Min;
		}
	}
	return res;
}
int mp[55][55];
int main()
{
	int m,k,i,j,a,b;
	while(scanf("%d%d%d",&n,&m,&k),n+m+k)
	{
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				map[i][j]=mp[i][j]=0;
		for(i=1;i<=m;i++)
		{
			scanf("%d%d",&a,&b);
			mp[a][b]=1;
			map[b][a]=1;
			map[a][b]=1;
		}
		bfs(1);
		for(i=1;i<=n;i++)bdis[i]=dis[i];
		bfs(n);
		for(i=1;i<=n;i++)hdis[i]=dis[i];

		for(i=1;i<=2*n;i++)
			for(j=1;j<=2*n;j++)
				cap[i][j]=0;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
				if(mp[i][j])
					cap[i+n][j]=inf;
			if(bdis[i]+hdis[i]<=k)
				cap[i][i+n]=1;
		}
		cap[1][1+n]=inf;
		cap[n][n+n]=inf;
		printf("%d
",maxflow(1,n+n));
	}
	return 0;
}