#include <fstream>

using namespace std;

ifstream fi("bfs.in");
ofstream fo("bfs.out");

typedef struct 
	node
	{
		int date;
		node *next;	
	}*list;

node *head, *temp, *tail, *Lda[100005];

int n, m, Mx, M[100005], x, y, i, l, k, dr=1, st=1, Q[100005], s;
bool viz[100005];

void add(node *&head, int q)
{
	node *temp=new node;
	temp->date=q;
	temp->next=head;
	head=temp;
}

void bfs(int q)
{
	st=1;
	dr=1;
	while (st<=dr)
	{	
		
		for(node *temp=Lda[Q[st]]; temp; temp=temp->next)
		if(!viz[temp->date])
		{
			viz[temp->date]=1;
			Q[++dr]=temp->date;
			M[temp->date]=M[q]+1;
		}
		q=Q[++st];
	}
	
	
}


int main()
{
	fi >> n >> m >> s;
	
	for(i=1; i<=n; i++) Lda[i]=NULL;
	
	for(i=1; i<=m; i++)
	{
		fi >> x >> y;
		add(Lda[x],y);	
	}
	
	Q[1]=s;
	viz[s]=1;
	bfs(s);

	for(i=1; i<=n; i++)
	if(M[i]) fo << " " << M[i]; 
	else if(i==s) fo << " 0"; else fo << " -1";	
	
	
	
}