/// bril.cpp : Defines the entry point for the console application.

    //



    #include "stdafx.h"

    //#include <fstream>

#include <cstdio>

#include <stdio.h>
#include<vector>

    using namespace std;



#define min(a,b) (a>b?b:a)

#define max(a,b) (a<b?b:a)





//ifstream fin("arbint.in");

//ofstream fout("arbint.out");



FILE *fin, *fout;






/*
unsigned long long rplN, rplP, rplR=1999999973ULL;

void doo(){
    unsigned long long t=1;
    for(unsigned long long i=1ULL;i<=rplP;i*=2ULL){
        if(i&rplP){
            t*=rplN;
            t%=rplR;
            }
        rplN*=rplN;
        rplN%=rplR;
        }
    fprintf(fout,"%llu",t);
    }
    */


int n,m,d[100010],s,q[100010];
vector<int> v[100010];

void myRead(){
    fscanf(fin,"%d%d%d",&n,&m,&s);
    int x,y;
    for(int i=1;i<=m;++i){
        fscanf(fin,"%d%d",&x,&y);
        v[x].push_back(y);
        }
    }


void doo(){
    q[1]=s;
    int p=1,e=1;
    while(p<=e){
        int nod=q[p];
        for(int i=0;i<v[nod].size();++i){
            if(v[nod][i]!=s&&d[v[nod][i]]==0){
                ++e;
                q[e]=v[nod][i];
                d[q[e]]=1+d[nod];
                }
            }
        ++p;
        }
    for(int i=1;i<n;++i)
        if(d[i]!=0)
            fprintf(fout,"%d ",d[i]);
        else
            fprintf(fout,"%d ",i==s?0:-1);
    if(d[n]!=0)
        fprintf(fout,"%d\n",d[n]);
    else
        fprintf(fout,"%d\n",n==s?0:-1);
    }


/*
int noduri[270010];

int n, m,a,b;





void constr(int poz, int left, int right) {

    if (left == right) {

        //fin >> noduri[poz];

        //fscanf_s(fin, "%d", &noduri[poz]);

        fscanf(fin, "%d", &noduri[poz]);



        }

    else {

        int mid = (left + right) / 2;

        constr(2 * poz, left, mid);

        constr(2 * poz+1, mid+1, right);



        noduri[poz] = max(noduri[2 * poz], noduri[2 * poz + 1]);

        }

    }





void do1(int poz, int left, int right) {

    if (left == a&&right == a)

        noduri[poz] = b;

    else {

        int mid = (left + right) / 2;

        if (a <= mid)

            do1(2*poz, left, mid);

        else

            do1(2*poz+1, mid+1, right);

        noduri[poz] = max(noduri[2 * poz], noduri[2 * poz + 1]);

        }

    }



int do0(int poz, int a, int b, int left, int right) {

    if (left == a&&right == b)

        return noduri[poz];

    int mid = (left + right) / 2;

    if (b <= mid)

        return do0(2*poz, a, b, left, mid);

    if (a <= mid&&b > mid){
        int x1=do0(2 * poz, a, mid, left, mid), x2=do0(2 * poz + 1,mid+1,b, mid+1, right);
        return max(x1,x2);
        }

    if (a > mid)

        return do0(2 * poz+1, a, b, mid+1, right);

    return 0;



    }




    */
int main()

    {



    //errno_t err;

    //err = fopen_s(&fin, "arbint.in", "r");

    //err = fopen_s(&fout, "arbint.out", "w");

    fin=fopen( "bfs.in", "r");

    fout=fopen("bfs.out", "w");

    //fin >> n >> m;

    //fscanf(fin, "%llu%llu", &rplN,&rplP);

    //fscanf_s(fin, "%d%d", &n, &m);

    /*

    constr(1,1,n);

    int x, y, z;

    for (int i = 1; i <= m; ++i) {

        fscanf(fin, "%d%d%d", &x, &a,&b);

        //fscanf_s(fin, "%d%d%d", &x, &y, &z);

        if (x == 0)

            //fout << do0(1,y,z)<<"\n";

            fprintf(fout, "%d\n", do0(1,a,b,1,n));

        else

            do1(1,1,n);

        }
        */
    myRead();
    doo();

    fclose(fin);

    fclose(fout);

    return 0;

    }