/// Craciun Catalin
///  BFS
///   www.infoarena.ro/problema/bfs
#include <fstream>
#include <iostream>
#include <vector>

#define NMax 100005
#define MMax 1000005

using namespace std;

ifstream f("bfs.in");
ofstream g("bfs.out");

struct cod{

    long nod;
    long cost;
};

long n,m,s;
vector<long> A[NMax];
cod C[MMax];
bool viz[NMax];
int CT[NMax];

void bfs()
{
    long prim=1, ultim=1;

    while (prim<=ultim)
    {
        int el=C[prim].nod;
        viz[el]=true;
        prim++;
        long len=A[el].size();

        for (long i=0;i<len;i++)
        {
            if (!viz[A[el][i]])
            {
                ultim++;
                C[ultim].nod=A[el][i];
                C[ultim].cost=C[prim-1].cost+1;
                viz[A[el][i]]=true;
                CT[A[el][i]]=C[ultim].cost;
            }
        }
    }
}

void citire()
{
    f>>n>>m>>s;
    for (long i=1;i<=m;i++)
    {
        long x,y;

        f>>x>>y;
        A[x].push_back(y);
    }

    f.close();
}

int main()
{
    citire();

    for (int i=1;i<=n;i++)
        CT[i]=-1;
    CT[s]=0;

    C[1].nod=s;
    C[1].cost=0;

    bfs();

    for (int i=1;i<n;i++)
        g<<CT[i]<<' ';
    g<<CT[n]<<'\n';
    g.close();

    return 0;
}