#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int N=1<<17;
vector<int> a[N];
int q[N],mut[N],p,u;
int n,m,s;
inline void push(int x)
{
	q[++u]=x;
}
inline bool empty()
{
	return u==p-1;
}
inline int front()
{
	return q[p];
}
inline void pop()
{
	++p;
}
void read()
{
	int x,y;
	scanf("%d%d%d",&n,&m,&s);
	while(m--)
	{
		scanf("%d%d",&x,&y);
		a[x].push_back(y);
	}
}
void vec(int x)
{
	
	int z=a[x].size();
	for(int i=0;i<z;++i)
		if(mut[a[x][i]]==-1)
		{
			push(a[x][i]);
			mut[a[x][i]]=mut[x]+1;
		}
}
void bfs()
{
	p=1;
	push(s);
	mut[s]=0;
	while(!empty())
	{
		int baz=front();
		vec(baz);
		pop();
	}
}
int main()
{
	freopen("bfs.in","r",stdin);
	freopen("bfs.out","w",stdout);
	read();
	for(int i=1;i<=n;++i)
		mut[i]=-1;
	bfs();
	for(int i=1;i<=n;++i)
		printf("%d ",mut[i]);
	return 0;
}