#include<cstdio>
#include<vector>
#include<queue>
#define NMAX 100001

using namespace std;
vector<int> v[NMAX];
vector<int>::iterator it;
queue<int> q;
int main()
{
int n,m,s,x,y;
freopen("bfs.in","r",stdin);
freopen("bfs.out","w",stdout);
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
v[x].push_back(y);
}
vector<int> d(n+1,-1);
d[s]=0;
q.push(s);
while(!q.empty())
{
s=q.front();
q.pop();
for(it=v[s].begin();it!=v[s].end();++it)
	if(d[*it]<0)
	{
		d[*it]=d[s]+1;
		q.push(*it);
	}
}

for(it=d.begin();it!=d.end();++it)
	printf("%d ",*it);
return 0;
}