#include<cstdio>
using namespace std;
int x,y,n,m,k,i,j,nd,cap[202][202],drum[202],a[202][202],flux[202][202],viz[202],st[202],q,l[202],niv[202];
void elimindf(int nd,int nv)//se face cu bf nu df
{int c[203]={0},p=1,u=1,s[202]={0},ok=1;//s tine minte cate noduri trb sa iau pt fiecare nivel
   c[1]=nd;viz[nd]=1;
    niv[nd]=1;
	while(p<=u)
	{
		nd=c[p]; //daca am completat nodurile dupa un nivel nv++;
		if(s[nv]){ok=1; nv++;}//creste daca am luat toate de pe nivelul anterior
	   if(niv[nd]==k)st[++q]=nd;
	   for(i=1;i<=n;i++)
	   {
		 if(a[nd][i] && !viz[i])
		 {
		  viz[i]=1; 
		  niv[i]=niv[nd]+1;
		   if(niv[nd]<=k)cap[nd][i]=a[nd][i];
		  c[++u]=i;
		 if(ok)s[nv]++;
		 }
	   }
	   ok=0;//atentie la distante
	  s[nv]--;
	  p++;
	}
	
}

int abs(int nr)
{
	if(nr>-1)return nr;
	return -nr;
}
int minim(int a,int b)
{
	if(a<b)return a;
	return b;
}
int bfs(int s,int d)
{int u=1,p=1,nd=s,i,c[1001]={0};//nodul sursa = 1
  c[1]=s; viz[s]=1;
	while(p<=u && !viz[d])
	{
		for(i=1;i<=n+1;i++)
		  if(!viz[i])//daca am muchie de la nd la i
			if(flux[nd][i]<cap[nd][i])
			{ 
				c[++u]=i; viz[i]=nd;
			}
			else
			if(flux[i][nd]>0)
			{
				c[++u]=i; viz[i]=-nd;//avem arc saturat
			}
	  nd=c[++p];
	}
   return viz[d];//daca nu e vizitat fluxul este maxim
}

void ek(int s,int d)
{int a=110001,b=110001,minn,k,fluxmax=0;//maresc fluxul cu minimul lui a
	while(bfs(s,d))
	{
		k=0; l[k]=d;
		while(l[k]!=s)
		{
			k++;
			l[k]=abs(viz[l[k-1]]);//introduc in lant nodul care intra in nodul curent
			if(viz[l[k-1]]>0)
			  if(cap[l[k]][l[k-1]]>flux[l[k]][l[k-1]]) 
				a=minim(a,cap[l[k]][l[k-1]]-flux[l[k]][l[k-1]]);//minimul de marire de flux
			 else
		    if(viz[l[k-1]]<0)b=minim(b,flux[l[k-1]][l[k]]);
		}
		minn=minim(a,b);
		fluxmax+=minn;
		for(k;k>0;k--)
			if(viz[l[k-1]]>0)
			  flux[l[k]][l[k-1]]+=minn;
			else
			  flux[l[k-1]][l[k]]-=minn;
		for(i=1;i<=n+1;i++)viz[i]=0;
	}

	printf("%d",fluxmax);
}

int main()//drumuri distincte cu flux
{
	freopen("traseu.in","r",stdin);freopen("traseu.out","w",stdout);
	scanf("%d %d %d %d",&n,&m,&nd,&k);
	for(i=1;i<=m;i++)
	{
	  scanf("%d %d",&x,&y);
	  a[x][y]=a[y][x]=1;
	}
	elimindf(nd,1);
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(niv[i]<=k && niv[j]<=k)cap[i][j]=a[i][j];
	for(i=1;i<=q;i++)
		cap[st[i]][n+1]=32767;
	for(i=1;i<=n;i++)viz[i]=0;
	ek(nd,n+1);
return 0;}