#include <fstream>
#include <algorithm>

using namespace std;
ifstream f1("bfs.in");
ofstream f2("bfs.out");
#define M 1000017
#define N 100017

int s, x, n,m,i,j;

struct arc
        {
            int x,y;
        };

arc a[M],d[N];
int dist[N], poz[N] ; // poz - pozitia in care apare primul arc cu x-ul i in vectoru a sortat
int coada[N], l, r;    // structura coada

void interclas(int st, int dr, int m)
{

    int i=st, j=m+1, k= st ;

    while (i<=m && j<=dr )
        if (a[i].x < a[j].x )
               d[ k++ ]= a[ i++ ];
               else d[k++]= a[ j++ ];

    while ( i<=m ) d[ k++ ]= a[ i++ ];
    while ( j<=dr ) d[ k++ ]= a[ j++ ];

    for (i=st; i<=dr; i++)
        a[i]=d[i];
}

void merge_sort(int st, int dr)
{
    if (st>=dr) return;

    int m=(st+dr)/2;

    merge_sort(st, m);
    merge_sort(m+1,dr);

    interclas(st, dr, m);
}

void BFS(int s) //////////////////////// parcurgere in latime
{
    coada[++l]=s;
    r=1;
    int pas=-1;

    while (l<=r )   // cat se poate duce pe la vecini
    {
        int stop= r, i, nod;
        pas++;

        while (l<=stop) // bag in coada vecinii nodurilor curente
        {
            nod= coada[ l++ ];    // se creste l

            dist[ nod ]= pas;     // <== notez distanta

            i= poz[ nod ];

            while (i && a[i].x == nod ) // vizitez vecinii nodului nod
            {
                if ( dist[ a[i].y ] == -1 ) // n-a fost nimeni pe aici
                    {
                        coada[ ++r ]= a[i].y;
                        dist[ a[i].y ]= pas+1;
                    }
                i++;
            }

        }
    }

}

int main()
{
    f1>>n>>m>>s;
    for (i=1; i<=m; i++)
        f1>>a[i].x>>a[i].y;

    merge_sort(1,m);

    for (i=1; i<=m; i++)
        if ( poz[ a[i].x ] == 0 )
            poz[ a[i].x ]= i;

    for (i=1; i<=n; i++)
        dist[i]= -1;

    BFS(s);

    for (i=1; i<=n; i++)
        f2<<dist[i]<<" ";

    f2.close();
    return 0;
}