#include<fstream>
#include<vector>
#include<cstdlib>
#include<deque>
using namespace std;

ifstream in("bfs.in");
ofstream out("bfs.out");	
unsigned int n,m,i,j,s,x,y;

int main ()
{
	in>>n>>m>>s;
	
	vector<vector<int> > v;
	v.resize(100001);
	for(i=1;i<=m;i++)
		{
			in>>x>>y;
			v[x].push_back(y);
			
		}
	deque<int> p;
	vector<int> nr(100001,-1);
	nr[s]=0;
	p.push_back(s);
	while(!p.empty())
		{	
			while(!v[p[0]].empty())
			{
				p.push_back(v[p[0]][v[p[0]].size()-1]);
				if(nr[v[p[0]][v[p[0]].size()-1]]==-1)
					nr[v[p[0]][v[p[0]].size()-1]]=nr[p[0]]+1;
				v[p[0]].pop_back();
				
			}
			p.pop_front();
		}
	for(i=1;i<=n;i++)
		out<<nr[i]<<" ";
	return 0;
}