#include <fstream>
#include <string.h>
using namespace std;
ifstream f1("bfs.in");
ofstream f2("bfs.out");

#define N 1000*101

struct nod
{
    int val, next;
};

class coada
{
    int k;
    int c[N];

public:
    coada();
    void add(int x);
    int extract();
    bool empty() {return !k;};
};

class vect_liste
{
    int nr, iter, poz;
    int first[N], last[N];
    nod L[N];

public:
    vect_liste();
    void add( int x, int val );
    void set_iter(int x);       // ca sa pot afla numerele din lista x
    int give_next();
};

class graf
{
    int n,m, s;
    int dist[N];
    vect_liste VL;

public:
    graf();
    void read();
    void BFS();
    void print_dist();
};
        // ------------------------------------- coada -------------------------------------------
coada::coada()
{
    k=0;
    memset(c, 0, sizeof(c));
}

void coada::add(int x)
{
    c[++k]= x;
}

int coada::extract()
{
    if (k)
        return c[k--];
    else return 0;
}
            // ---------------------------------------- vect_liste -----------------------------
vect_liste::vect_liste()
{
    nr=0;
    memset(first, 0, sizeof(first) );
    memset(last, 0, sizeof(last));
    memset(L, 0, sizeof(L));
}

void vect_liste::add( int x, int val )
{
    L[++nr].val= val;

    L[last[x] ].next = nr;
    last[x]=nr;
    if (!first[x] )
        first[x]=nr;
}

void vect_liste::set_iter(int x)
{
    poz=first[x];
    iter=x;
}

int vect_liste::give_next()
{
    int p1= poz;
    poz= L[poz].next;
    return L[p1].val;
}
                        // --------------- graf -----------------------------------
graf::graf()
{
    memset(dist, -1, sizeof(dist));
}

void graf::read()
{
    f1>>n>>m>>s;

    int i,x,y;
    for (i=1; i<=m; i++)
        {
            f1>>x>>y;
            VL.add(x,y);
        }
}

coada c1, c2;

void graf::BFS()
{
    int x, v, pas=0;

    c1.add(s);
    while (!c1.empty() )
    {
        while (!c1.empty())
        {
            x= c1.extract();
            VL.set_iter(x); // setez iteratorul pe x ca sa vad vecinii lui

            v= VL.give_next();
            while ( v  )
            {
                if ( dist[v] == -1 )
                {
                    c2.add( v );
                    dist[v]= pas+1;
                }
                v= VL.give_next();
            }
        }
        while (!c2.empty())
            c1.add( c2.extract() );
        pas++;
    }

    dist[s]=0;
}

void graf::print_dist()
{
    for (int i=1; i<=n; i++)
        f2<<dist[i]<<" ";
}


int main()
{
    graf g;
    g.read();
    g.BFS();
    g.print_dist();

    f2.close();
    return 0;
}