#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>

using namespace std;

ifstream fin ("bfs.in");
ofstream fout ("bfs.out");

const int NMAX=1000000;

int n , m,s, l ;
vector <int>lista[NMAX];
int cost[NMAX], coada[NMAX];

int numar (int z)
{
    return lista[z].size();
}

void bfs(int nod)
{
    memset (cost, -1, sizeof (cost));
l=1;
cost[s]=0;
coada[l]=nod;

 for (int i = 1; i <= l; i++)
        for (int j = 0; j < numar(coada[i]); j++)
            if (cost[lista[coada[i]][j]] == -1)
            {
                coada[++l] = lista[coada[i]][j];
                cost[coada[l]] = cost[coada[i]] + 1;
            }

}


void citire()
{
	fin>>n>>m>>s;
	int x, y;
	for (int i=1; i<=m; ++i)
	{
		fin>>x>>y;
		lista[x].push_back(y);
	}


}

int main()
{
    citire();
bfs(s);
for (int i=1; i<=n; ++i)
    fout<<cost[i]<<" ";
    return 0;
}