#include <fstream>
#include <iostream>
using namespace std;
#define MAX 100001
int n, * a[MAX] , d[100001],s;

void read(){
	ifstream fin("bfs.in");
	int m;
	fin>>n>>m>>s;
	for(int i  =1;i<=n;i++)
		a[i] = new int [n+1],d[i] = -1;
	for( ; m ;--m){
		int i,j;
		fin>>i>>j;
		a[i][j] = 1;
		}
	fin.close();
	}
void bfs(){
	int *coada=new int[n+1], st =1, dr=1, k ,i ;
	coada[1] = s;
	d[s]=0;
	while(st <= dr )
	{
		k = coada[st];
		for(i=1; i <=n ;i++)
			if(a[k][i] == 1 && d[i] == -1){
					coada[++dr] = i;
					d[i] = d[k] +1;
				}
		st++;
		}
	}
void write(){
	ofstream fout("bfs.out");
	for(int i  =1 ;i<=n;i++)
		fout<<d[i]<<" ";
	fout.close();
	}

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