#include <fstream>
#include <queue>

using namespace std;

ifstream f("bfs.in");
ofstream g("bfs.out");

int a[10005][10005],v[100005],x,y,p,i,n,m,s,k;
queue<int> q;

int main()
{
	f>>n>>m>>s;
	
	for (i=1;i<=m;i++)
	{
		f>>x>>y;
		a[x][y]=1;
	}
	
	q.push(s);v[s]=1;
	
	while (!q.empty())
	{
		p=q.front();
		for (i=1;i<=n;i++)
		{
			if ((a[p][i]==1)&&(v[k]==0))
			{
				q.push(i);
				v[i]=v[p]+1;
			}
		}
		q.pop();
		
	}
	for(i=1;i<=n;i++) g<<v[i]-1<<' ';
}