#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
queue <int> c;
#define n 100000
#define m 1000000
vector <int> graf[n];
int N , M , inceput;
int drum[n];
int viz[n];
int nrarce;

void citire()
{
	scanf ("%d %d" , &N , &M );
	scanf ("%d" , &inceput);
	while (M--)
	{
		int x , y;
		scanf ("%d %d\n" , &x , &y);
		graf[x].push_back(y);
	}
	c.push(inceput);
	viz[inceput] = 1;
	drum[inceput] = 0;
}
void bfs()
{
	while (!c.empty())
	{
		int nod = c.front();
		c.pop();
		for (int i = 0 ; i < graf[nod].size() ; ++i)
		{
			if (!viz[graf[nod][i]])
			{
				nrarce++;
				viz[graf[nod][i]] = 1;
				c.push(graf[nod][i]);
				drum[graf[nod][i]] = nrarce;
			}
		}

	}
}
void afisare()
{
	for (int i = 1 ; i <= N ; ++i)
		printf ("%d ", drum[i]);
}
int main()
{
	freopen ("bfs.in", "r", stdin);
    freopen ("bfs.out", "w", stdout);
	memset (drum , -1 , sizeof(drum));
    citire();
    bfs();
    afisare();
	return 0;
}