#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;
	
	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 (;!d.empty();++s)
	{
		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());
			v[i].pop_back();
		}
	}
for (i=1;i<=n;++i) printf("%d ",sol[i]-1);
return 0;}