#include<fstream>
#include<iostream>
using namespace std;

int a[10][10],vizitat[10],c[10],n,prim,ultim,k,p[10],x=0,S,M;

void citeste(){
    fstream f("bfs.in",ios::in);
    int i,j,cx,cy;
    f>>n;
    f>>M;
    f>>x;
    while(!f.eof()){
    f>>cx;
    f>>cy;
    a[cx][cy]=1;
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){

            if(a[i][j]!=1)

                a[i][j]=0;
        }
        }
    f.close();
    }

void zero(){
    for(int i=1;i<=n;i++){
            vizitat[i]=0;
            p[i]=0;
            }
    }

void init(int k){
    prim=ultim=1;
    c[ultim]=k;
    vizitat[k]=1;
    p[k]=0;

    }
int este_vida(){

    return ultim<prim;}

void adauga(int i,int k){
    ultim++;
    c[ultim]=i;
    vizitat[i]=1;
    p[i]=k;
    }





void prelucrare(){
    int i;
    k=c[prim];
    for(i=1;i<=n;i++)
        if(a[k][i]==1&&vizitat[i]==0)
                adauga(i,k);

    prim++;
    }
    void afisare(){
        int i,j,este,y,d[10];
            fstream f2("bfs.out",ios::out);
        for(j=1;j<=n;j++)
            {

                for(i=0,este=0;i<=ultim && !este; i++)
                    if(c[i]==j) este =1;
                    if(este==1){
                        y=p[j]; i=0;
                        while(y){
                            i++;
                            d[i]=y;
                            y=p[y];
                            }

                                f2<<i<<" ";

                        }else f2<<-1<<" ";

                }

        }

int main(){
    citeste();

zero();
init(x);

       while(!este_vida()) prelucrare();

        afisare();



}