#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
//Restrictii
//2 <= N <= 100 000
//1 <= M <= 1 000 000
//Daca nu se poate ajunge din nodul S la nodul i, 
//atunci numarul corespunzator numarului i va fi - 1.


ifstream f("bfs.in");
ofstream g("bfs.out");
vector<int> v[100000];
queue<int> q;
int nod_vazut[100000];
int dist[100000];

void init_array(int n) {
    for (int i = 1; i <= n; i++)
        dist[i] = -1; //initializare array distante intre noduri vecine
}

void determina_vecini(int m) {
    int x, y;
    for (int i = 0; i < m; i++) {
        f >> x >> y;
        v[x].push_back(y);
    }
}

void BFS(int s)
{
    int p; //variabila pentru capul cozii
    dist[s] = 0; //distanta de la start la start e 0 si stim asta din date
    q.push(s); //adaugam nodul de start in coada
    nod_vazut[s] = 1;//notam ca am parcurs nodul de start s
    while (!q.empty())    { //cat timp avem elemente in coada
        p = q.front(); //capul cozii va fi stocat in p
        q.pop(); //apoi imediat scoatem capul cozii din coada
        for (int vecin : v[p]) //pentru fiecare din vecinii posibili ai elementului p
            if (!nod_vazut[vecin]) { //daca nodul vecin nu a fost vazut
                dist[vecin] = dist[p] + 1; //inseamna ca distanta de la p la vecin creste cu 1
                q.push(vecin);//punem vecinul in coada
                nod_vazut[vecin] = 1;//notam ca l-am parcurs
            }
    }
}

int main() {
    /* 5 7 2   //nr_noduri nr_muchii nod_start    (bfs.in)
     1 2
     2 1
     2 2
     3 2
     2 5
     5 3
     4 5*/
    int n, m, s;
    f >> n >> m >> s;

    init_array(n);
    determina_vecini(m);//verificare pentru toate muchiile
    BFS(s);  //s e nod start citit

    //scrierea distantelor fata de nod_start, in g
    for (int i = 1; i <= n; i++)
        g << dist[i] << ' ';
    f.close();
    g.close();
	return 0;
}