/*
 	Parcurgerea in latime. 
	Implementare cu liste de adiacenta implementate prin liste alocate dinamic.
 */

#include <fstream>
#include <iostream>
#include <cstdlib>
#define MAX 100001
using namespace std;
struct nod {
	int capat;
	nod * next;
};

nod * a[MAX];
int v[MAX], coada[MAX], dist[MAX], s, n;

void read();
void bfs();
void write();

void read(){
	int m;
	ifstream fin("bfs.in");
	fin>>n>>m>>s;
	for(int i = 1;i<=n;i++)
		a[i] = NULL;
	for( ; m ; m--){
		int i,j;
		fin>>i>>j;
		nod * p = new nod;
		p -> capat = j;
		p -> next = a[i];
		a[i] = p;
	}
	fin.close();
}

void write(){
	ofstream fout("bfs.out");
	for (int i = 1 ; i <= n ; i++)
		fout<<dist[i] <<" ";
	fout.close();
}

void bfs(){
	nod *st, *dr;
	st = dr = new nod;
	dr->next = NULL;
	dr->capat = s;
	v[s] = 1;
	for(int i = 1;i<=n;i++)
		dist[i] = -1;
	dist[s] = 0;
	while(st){
		int k = st -> capat;
		for(nod * p = a[k] ; p ; p = p->next)
			if(v[p->capat] == 0 ){
				v[p->capat] = 1;
				dist[p->capat] = dist[k] +1;
				nod * q = new nod;
				q->capat = p->capat;
				q->next = NULL;
				dr->next = q;
				dr = q;
			}
		nod * p  = st;
		st = st -> next;
		delete p;
	}
}

int main(){
	read();
	bfs();
	write();
	return 0;
}