#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define DMax 100001
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");

vector <int> Lista[DMax];
int n,m,s;

void Citire()
{
    int i,x,y;
    fin>>n>>m>>s;
    for(i=1;i<=m;i++){
        fin>>x>>y;
        Lista[x].push_back(y);
    }fin.close();
}

void Afis_lista(){
    int i,j;
    for(i=1;i<=n;i++){ cout<<i<<": ";
        for(j=0;j<Lista[i].size();j++) cout<<Lista[i][j]<<" ";
        cout<<'\n';
    }
}
bool seen[DMax];
int distanta[DMax];
void BFS(){

    int i;
    for(i=1;i<=n;i++) distanta[i]=-1;
    seen[s]=true;
    distanta[s]=0;
    queue <int> q;
    q.push(s);
    while(!q.empty()){
        int v=q.front();
        q.pop();
        for(i=0;i<Lista[v].size();i++){
            if(!seen[Lista[v][i]]){
                q.push(Lista[v][i]);
                seen[Lista[v][i]]=true;
                distanta[Lista[v][i]]=distanta[v]+1;
            }
        }
    }
}

void Afis_drum(){
    int i;
    for(i=1;i<=n;i++){
        fout<<distanta[i]<<" ";
    }
}

int main()
{
    Citire();
    //Afis_lista();
    BFS();
    Afis_drum();
    return 0;
}