//
//  bfs.cpp
//  Parcurgerea BFS
//
//  Created by Andrei Constantinescu on 2/26/13.
//  Copyright (c) 2013 Andrei Constantinescu. All rights reserved.
//
#include <fstream>
#include <vector>
#define Max 100010

using namespace std;

ifstream fin ("bfs.in");
ofstream fout ("bfs.out");

vector <int> V[Max];

int n,m,s;
int rez[Max],coada[Max],nr;

void bfs() {
    for (int i=0;i<=n;i++)
        rez[i]=-1;
    coada[nr++]=s;
    rez[s]=0;
    
    for (int i=0;i<nr;i++) {
        for (typeof V[coada[i]].begin() j=V[coada[i]].begin();j<V[coada[i]].end();j++)
            if (rez[*j]==-1) {
                rez[*j]=rez[coada[i]]+1;
                coada[nr++]=*j;
            }
    }
    for (int i=1;i<=n;i++)
        fout<<rez[i]<<" ";
}

int main () {
    int x,y;
    fin>>n>>m>>s;
    for (int i=0;i<m;i++) {
        fin>>x>>y;
        V[x].push_back(y);
    }
    bfs();
    return 0;
}