#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

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

///BFS
//Fiind dat un nod S, sa se determine, pentru fiecare nod X, numarul minim de arce ce trebuie parcurse pentru a ajunge din nodul sursa S la nodul X.

//N M S
//N = NR NODURI, M = NR MUCHII S = NOD SURSA
//Daca nu se poate ajunge din nodul S la nodul i, atunci numarul corespunzator numarului i va fi -1.

const int nmax=100005;
int d[nmax+1]; ///d[i] = lungimea drumului determinat de algoritm de la s la i = nivelul lui i în arborele asociat parcurgerii
int viz[nmax+1]; ///ce vârfuri au fost vizitate (descoperite) deja
int tata[nmax+1]; /* Atunci când vârful ˘
                            j este descoperit ca vecin nevizitat al lui i ¸si introdus în coada vom atribui lui ˘ tata[j] valoarea i (j este fiu
                            al lui i în arbore).
                        */
vector<int> G[nmax+1]; ///g[i] = lista nodurilor cu care are muchie i
 void bfs(int s)
 {
    queue<int> q;
    q.push(s);
    viz[s] = 1;
    d[s] = 0;
    while(!q.empty())
    {
        int i = q.front();
        q.pop();
        //cout<<i;
        for(auto next: G[i]) //se parcurge lista de adiacenta a nodului x pt a-i gasi vecinii
        {
            if(!viz[next]) //daca e vecin nevizitat e urmatorul pe care se aplica DFS
            {
                q.push(next);
                viz[next] = 1;
                tata[next] = i;
                d[next] = d[i] +1;
            }
        }
    }
 }

int main()
{
    int n,m,s;
    fin>>n>>m>>s;
    for(int j = 1; j<=n; j++)
        d[j] = -1;
    for(int j = 1; j<=m; j++)
    {
        int x,y;
        fin>>x>>y;
         G[x].push_back(y); //adaugam in lista de adiacenta a lui x: nodul y
        //G[y].push_back(x); //adaugam si in lista lui y: nodul x (e graf neorientat)

    }
    bfs(s);

    /*
    for(int j = 1; j<= n; j++)
    {
        if(viz[j] == 0)
            bfs(j);
    }
*/ //pt aceasta problema nu ne intereseaza bfs pt tot, ci doar din sursa ca sa vedem cate noduri atinge
    for(int j=1;j<=n; j++)
        fout<<d[j]<<" ";
    return 0;
}