/*
#include <iostream>
#include <fstream>
using namespace std;
ifstream f;
int n,m,t;
int mat[101][101];
void graf_construire(int t){
    int i,j,k;
    for(i=0;i<m;i++){
        f>>j>>k;
        mat[j][k]=1;
        if(t==0)mat[k][j]=1;
    }
}
void graf_afisare(){
    int i,j;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++)
            cout<<mat[i][j]<<' ';
        cout<<endl;
    }
}
int main(){
    f.open("graf.in");
    f>>n>>m>>t;
    graf_construire(t);
    f.close();
    graf_afisare();
    return 0;
}



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

ifstream f;
int n,m,t;
vector<vector<int>> lista_adiacenta;

void lista_construire(int t){
    int i,j,k;
    for(i=0;i<m;i++){
        f>>j>>k;
        lista_adiacenta[j].push_back(k);
        if(t==0)lista_adiacenta[k].push_back(j);
    }
}
void lista_afisare(){
    int i,j;
    for(i=1;i<=n;i++){
        cout<<i<<": ";
        for(j=0;j<lista_adiacenta[i].size();j++)
            cout<<lista_adiacenta[i][j]<<' ';
        cout<<endl;
    }
}

int main(){
    f.open("graf.in");
    f>>n>>m>>t;
    lista_adiacenta.resize(n+1);
    lista_construire(t);
    f.close();
    lista_afisare();
    return 0;
}
*/

#include<iostream>
#include<fstream>
#include<queue>
#include<vector>

using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");

int n,m,s;
queue<int> coada;
int cost[100001];
vector<vector<int>> lista_adiacenta;

void lista_construire(){
    int i,j,k;
    for(i=0;i<m;i++){
        f>>j>>k;
        lista_adiacenta[j].push_back(k);
    }
}

void bfs()
{
    int element;
    while(!coada.empty()) {
        element=coada.front();
        coada.pop();
        int p;
        for(p=0;p<lista_adiacenta[element].size();p++)
            if(cost[lista_adiacenta[element][p]]==-1)
            {
                coada.push(lista_adiacenta[element][p]);
                cost[lista_adiacenta[element][p]]=cost[element]+1;
            }

    }

    for(int i=1;i<=n;i++)
        g<<cost[i]<<' ';
}

void lista_afisare(){
    int i,j;
    for(i=1;i<=n;i++){
        cout<<i<<": ";
        for(j=0;j<lista_adiacenta[i].size();j++)
            cout<<lista_adiacenta[i][j]<<' ';
        cout<<endl;
    }
}


int main()
{
    f>>n>>m>>s;
    int i,j;
    for(int i=1;i<=n;i++) cost[i]=-1;
    cost[s]=0;
    lista_adiacenta.resize(n+1);
    lista_construire();
    coada.push(s);
    bfs();
}


/*
int main()
{
    f>>n>>m>>s;
    lista_adiacenta.resize(n+1);
    lista_construire();
    lista_afisare();
}
*/