#include <fstream>
#include <stdlib.h>

using namespace std;

#define DEBUG false
#define MAXN 100000
#define MAXM 1000000

struct node {
    int start;
    int length;
}a[MAXN];

struct edge{
    int a,b;
}v[MAXM];

struct queue_item{
    int value, step;
    queue_item* next;
}*first, *last;

#if DEBUG
#include <iostream>
#define INFILE "/Users/biordach/Documents/Xcode Projects/training/training/bfs.in"
#define __OUT cout
#else
#define INFILE "bfs.in"
#define OUTFILE "bfs.out"
ofstream __OUT(OUTFILE);
#endif

int n, m, s;
int d[MAXN];
bool viz[MAXN];

void readInput();
void solve();
void printOutput();

int main(int argc, const char * argv[])
{
    readInput();
    solve();
    printOutput();

#if DEBUG == false
    __OUT.close();
#endif
    
    return 0;
}

void readInput(){
    ifstream in(INFILE);
    in>>n>>m>>s;
    s--;
    for(int i=0;i<m;i++){
        in>>v[i].a >> v[i].b;
        v[i].a--;
        v[i].b -- ;
    }
    in.close();
}

int sortf(const void *a, const void *b){
    edge *aa = (edge*)a, *bb = (edge*)b;
    return aa->a - bb->a;
}

void solve(){
    qsort(v, m, sizeof(edge), sortf);

    int current = v[0].a;
    int len = 1;
    a[current].start = 0;

    for(int i=1;i<m;i++){
        if(v[i].a == current){
            len ++;
        } else {
            a[current].length = len;
            current = v[i].a;
            a[current].start = i;
            len = 1;
        }
    }
    a[current].length = len;

#if DEBUG
    for(int i=0;i<m;i++)
        __OUT<<i << ' ' <<v[i].a<<' ' << v[i].b<<'\n';
    __OUT<<'\n';
    for(int i=0;i<n;i++)
        __OUT<<i<< ' ' <<a[i].start << ' '<< a[i].length<<'\n';
#endif
    
    for(int i=0; i<n;i++){
        d[i] = -1;
        viz[i] = false;
    }
    
    viz[s] = true;
    d[s] = 0;
    queue_item* q= new queue_item;
    q->value = s;
    q->step = 0;
    q->next = NULL;
    first = last = q;
    
    int left = n-1;
    while(left > 0 && first != NULL){
        for(int i = 0; i < a[first->value].length;i++)
            if(!viz[v[i+a[first->value].start].b]){
                int bla = v[i+a[first->value].start].b;
                q = new queue_item;
                q->value = bla;
                q->step = 1 + first->step;
                q->next = NULL;
                viz[bla] = true;
                last->next = q;
                last = q;
                left --;
                d[bla] = q->step;
            }
        q = first->next;
        delete first;
        first = q;
    }
}

void printOutput(){
    for(int i=0;i < n; i++)
        __OUT<<d[i]<<' ';
    __OUT<<'\n';
}