#include<fstream>
#include<queue>
#include<vector>
using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");
#define NM 100001
vector<int>d[NM],dist;
vector<int>::iterator it;
queue<int>q;
int N,M,S,x,y,i;
int main()
{	f>>N>>M>>S;
	for(i=1;i<=M;i++)
	{	f>>x>>y; d[x].push_back(y); }
	q.push(S) , dist.resize(N+1,-1);
	dist[S]=0;
	while(!q.empty())
	{	x=q.front() , q.pop();
		for(it=d[x].begin();it!=d[x].end();it++)
		{	if(dist[*it]==-1)
				dist[*it]=dist[x]+1 , q.push(*it);
			else
				if(dist[*it]>dist[x]+1)
					dist[*it]=dist[x]+1 , q.push(*it);
		}
	}
	for(it=dist.begin()+1;it!=dist.end();it++)
		g<<*it<<" ";
	f.close();
	g.close();
	return 0;
}