#include<fstream>
#include<vector>
#include<queue>
#define NMAX 100010

using namespace std;

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

struct coada {int nod, nr;};

int n, m, s, vz[NMAX], drum[NMAX];
vector<int> a[NMAX];
queue<coada> q;

void Citeste()
{
	int i, x, y;
	f>>n>>m>>s;
	for (i=1; i<=m; ++i)
	{
		f>>x>>y;
		a[x].push_back(y);
		//a[y].push_back(x);
	}
	for (i=1; i<=n; ++i) drum[i]=-1;
}

void Bfs()
{
	int i, lg, x;
	coada r, w;
	
	vz[s]=1; drum[s]=0; r.nod=s; r.nr=0; q.push(r);
	
	while (!q.empty())
	{
		r=q.front(); q.pop(); lg=a[r.nod].size();
		for (i=0; i<lg; ++i)
		{
			x=a[r.nod][i];
			if (!vz[x])
			{
				vz[x]=1; drum[x]=r.nr+1; 
				w.nr=drum[x]; w.nod=x;
				q.push(w);
			}
		}
	}
}

void Scrie()
{
	int i;
	g<<drum[1];
	for(i=2; i<=n; ++i) g<<" "<<drum[i];
	g<<"\n";
}

int main()
{
	Citeste();
	Bfs();
	Scrie();
	f.close();
	g.close();
	return 0;
}