#include<iostream>
#include<fstream>
using namespace std;
# define max 100000

struct nod{
	unsigned long int vec;
	nod *next;
};

struct coada{
	unsigned long int cost;
	unsigned long int vf;
	coada *next;
}*prim,*q;

struct vector{
	unsigned long int a;
	unsigned long int b;
}queue[max];


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

unsigned long int co[max]={0},s,viz[max]={0};
unsigned long int n,m;
unsigned long int st=1,dr=0;
nod *v[max];

void push(unsigned long int a, unsigned long int cost){
	dr++;
	queue[dr].a=a;
	queue[dr].b=++cost;
	co[a]=cost;	
}

int pop(){
	st++;
	return queue[st-1].b;
}



void citire(){
	f>>n>>m>>s;
	for(unsigned long int i=1;i<=n;i++)
		v[i]=NULL;
	for(unsigned long int i=1;i<=m;i++){
		unsigned long int x,y;
		f>>x>>y;
		if(v[x]==NULL){
			v[x]=new nod;
			v[x]->vec=y;
			v[x]->next=NULL;
		}
		else{
			nod *p=new nod;
			p->vec=y;
			p->next=v[x];
			v[x]=p;
		}
	}
}


int main(){
	q=NULL;
	citire();
	push(s,-1);
	viz[s]=1;
	while(st<=dr){
		nod *r=v[queue[st].a];
		unsigned long int c=pop();
		while(r!=NULL){
			if(viz[r->vec]==0){
			push(r->vec,c);
			viz[r->vec]=1;
			}
			r=r->next;
		}
	}
	for(unsigned long int i=1;i<=n;i++)
		if(i==s)
			g<<0<<" ";
	else
		if(co[i]==0)
				g<<-1<<" ";
			else
				g<<co[i]<<" "; 
return 0;
}