// Copyright (C) 2018 Gheoace Mihai - All Rights Reserved


#include<bitset>
#include<cstdlib>
#include <cstring>
#include <fstream>
#include <vector>
#define N 100002
#include <iostream>
std::bitset < N > viz;

typedef struct nod{
    int a;
    nod* urm;
} *Pnod;

Pnod v[N];
int S[N];  // stiva de noduri care  vor fi vizitate.
int Cost[N];  // distanta intre nodul x(de unde incepe bfs).
// si nodul i

void Push(Pnod &dest,int val)
{
    Pnod p;
    p = new nod;
    p->a = val;
    p->urm = dest;
    dest = p;
}
void dfs(int i)
{
    Pnod p;
    viz[i] = 1;
    for (p = v[i]; p != NULL; p = p->urm)
        if (!viz[p->a])
            dfs(p->a);
}
std::vector< std::string > nume;

void BFS(int rad){
    int l=1;
    // setam toate nodurile nevizitate.
    memset(Cost, -1, sizeof(int) * N);
    S[l] = rad;  // introduc nodul de start in coada.
    Cost[rad]=0;
    int i;
    for (i = 1; i <= l; ++i)  // parcurg nodurile din coada si se scot.
         for (Pnod p = v[S[i]]; p != NULL; p = p->urm)
            if( Cost[p->a] == -1){
                S[++l] = p->a;  // adaug nodul in coada.
                Cost[p->a]=Cost[S[i]]+1;  // salvez distanta nodul curent si tatal sau.
            }
}

int main(){
    int n, m;  // n-nr de coduri;m-nr de arce
    int x, y, i, s;
    std::string name;  // pt citirea numelor de orase

    std::ios::sync_with_stdio(false);
    std::ifstream f("bfs.in");
    std::ofstream g("bfs.out");
    f >> n >> m >> s;
    /*for (i = 0; i < 3; ++i){  // citesc numele oraselor
        fid >> name;
        nume.push_back(name);
        printf("%s ",(nume[i]).c_str());
    }*/
    for(i=0 ; i < m; ++i){  // citeste arcele sub forma unei liste de vecini.
        f >> x >> y;
        Push(v[x],y);
        // Push(v[y],x);.
    }
    BFS(s);
    for(i=1;i<=n;++i)
        g << Cost[i] << ' ';
    g << '\n';
}