#include <iostream>
#include <fstream>
#include <vector>
#define DIM 100005

using namespace std;

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

struct node{
    int val;
    node * next;
}*L[DIM];

int n,m,s;
bool used[DIM];
vector <int> d(DIM,-1);

void add(int x, int y){
    node *p = new node;
    p->val = y;
    p->next = L[x];
    L[x] = p;
}

void citire(){
    f>>n>>m>>s;
    int x,y;
    for(int i=1; i<=m; i++){
        f>>x>>y;
        add(x,y);
    }
}

void DFS(){
    int inc,sf, coada[DIM]; inc = sf = 0;
    coada[inc] = s;
    d[s] = 0;
    while(inc <= sf){
        node *p = L[coada[inc]];
        while(p){
            if(d[p->val] == -1){
                d[p->val] = d[coada[inc]] + 1;
                coada[++sf] = p->val;
            }
            p = p->next;
        }
        inc++;
    }
}

void afisare(int n, vector <int> v){
    for(int i=1; i<=n; i++)
        g<<v[i]<<" ";
}

int main() {
    citire();
    DFS();
    afisare(n,d);
}