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

const int NMAX=100000;
vector<int> v[NMAX];

void bfs(const int& s, const int& nr)
{
	queue<int> coada;

	coada.push(s);
	int vizitat[NMAX]={0};
	int distanta[NMAX];
	vizitat[s]=1;
	distanta[s]=0;
	for(int i=0;i<NMAX;i++)
		distanta[i]=-1;
	ofstream out("bfs.out");

	while(!coada.empty())
	{
		int nod=coada.front();
		coada.pop();
		for(int i=0;i<(int) v[nod].size();i++)
		{
			int node=v[nod][i];
			if(!vizitat[node])
			{
				distanta[node]=distanta[nod]+1;
				coada.push(node);
				vizitat[node]=1;
			}
		}
	}
	
	for(int i=0;i<nr;i++)
		out<<distanta[i]<<" ";
	out<<"\n";
	out.close();
}

int main()
{
	ifstream in("bfs.in");

	int n,m,s;
	in>>n>>m>>s;
	--s;
	int a,b;

	for(int i=0;i<m;i++)
	{
		in>>a>>b;
		--a;
		--b;
		v[a].push_back(b);
	}
	bfs(s,n);
}