#include<fstream>
#include<iostream>
using namespace std;
ifstream in("bfs.in");
ofstream out("bfs.out");
short int matr[10001][10001];
int viz[10001],coada[10001],dist[10001];
int n,m,s,i,st,fin,curent,x,y;
int main(){
in>>n>>m>>s; ///Varfuri arce sursa
for(i=1;i<=m;i++){
    in>>x>>y;
    matr[x][y]=1;
}
st=fin=1;
coada[1]=s;
viz[s]=1;
dist[s]=0;
while(st<=fin){
    curent=coada[st];
    for(i=1;i<=n;i++){
        if(matr[curent][i]==1&&viz[i]==0){
            cout<<i<<" ";
            fin++;
            coada[fin]=i;
            viz[i]=1;
            dist[i]=dist[curent]+1;
        }
    }
    st++;
    cout<<endl;
}
for(i=1;i<=n;i++){
    if(viz[i]==0)
        out<<-1<<" ";
    else
        out<<dist[i]<<" ";
}
return 0;
}