#include<stdio.h>
#include<stdlib.h>
#include<queue>
using namespace std;

int NrVf, NrArce;
int *List[100001];
int Vizited[100001];


void BFS(int start)
{
	queue<int> ToVisit;
	ToVisit.push(start);
	Vizited[start] = true;
	
	while (ToVisit.size() > 0)
	{
		int v = ToVisit.front();
	
		for (int i=1; i<=List[v][0]; i++)
			if (!Vizited[List[v][i]]) {
				ToVisit.push(List[v][i]);
				Vizited[List[v][i]] = Vizited[v]+1;
			}
		
		ToVisit.pop();
	}
}

inline void AddItem (int x, int y)
{
	List[x][0]++;
	List[x] = (int*) realloc(List[x], (List[x][0]+1)*sizeof(int));
	List[x][List[x][0]] = y;
}

int main()
{
	freopen("bfs.in", "r", stdin);
	freopen("bfs.out", "w", stdout);
	
	int Nod;
	
	scanf("%d %d %d\n", &NrVf, &NrArce, &Nod);
		
	// Init list
	for (int i=1; i<=NrVf; i++)
	{
		List[i] = (int*) realloc(List[i], sizeof(int));
		List[i][0] = 0;
	}
	
	// Citeste arce
	for (int i=1; i<=NrArce; i++)
	{
		int x,y;
		scanf("%d %d\n", &x, &y);
		AddItem(x,y);
	}
	
	BFS(Nod);
	
	for (int i=1; i<=NrVf; i++)
		printf("%d ", Vizited[i]-1);
	
	return 0;
}