#include<fstream>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int main()
{
	int n,m,s,dist=1;
	fstream fin("bfs.in", fstream::in);
	fstream fout("bfs.out", fstream::out);
	vector< vector<int> > graph;
	vector<int> distances;
	queue<int> Q;
	fin>>n>>m>>s;
	graph.resize(n+1);
	distances.resize(n+1);
	for(int i=0; i<m; ++i)
	{
		int x,y;
		fin>>x>>y;
		graph[x].push_back(y);
	}
	
	for(int i=1; i<=n; ++i)
	{
		/*for(int j=0; j<graph[i].size(); ++j)
			cout<<graph[i][j]<<" ";
		cout<<endl;*/
		distances[i]=-1;
	}
	
	Q.push(s);
	distances[s]=0;
	/*for(int i=0; i<graph[s].size(); ++i)
		if(graph[s][i]==s)
		{
			distances[s]=0;
			break;
		}*/
	
	while(!Q.empty())
	{
		int node=Q.front();
		Q.pop();
		for(int i=0; i<graph[node].size(); ++i)
		{
			if(distances[graph[node][i]]>0)
			{
				distances[graph[node][i]]=dist;
				Q.push(graph[node][i]);
			}
		}
		dist++;
	}
	
	for(int i=1; i<=n; ++i)
		fout<<distances[i]<<" ";
	fout<<endl;
	
	
	fin.close();
	fout.close();
	return 0;
}