#include <cstdio>
#include <vector>
#include <deque>
#define N 100003
#define pb push_back
#define f front
using namespace std;

vector <int> v[N];
deque <int> d;
int sol[N];

int main()
{
	int n,m,s,i,p=1,j;
	
	freopen("bfs.in","r",stdin);
	freopen("bfs.out","w",stdout);
	scanf("%d %d %d",&n,&m,&s);
	for (i=1;i<=m;++i)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		v[a].pb(b);
	}
	d.pb(s);sol[s]=1;s=2;
	for (;p;++s)
	  for (j=p,p=0;j>0;--j)
		{
		i=d.f();
		d.pop_front();
		while (!v[i].empty())
		{
			if (!sol[v[i].back()])
				sol[v[i].back()]=s,d.pb(v[i].back()),++p;
			v[i].pop_back();
		}
	    }
for (i=1;i<=n;++i) printf("%d ",sol[i]-1);
return 0;}