#include <fstream>
#include <iostream>
#include <string>
#include <queue>
#define nmax 100001

using namespace std;

struct Nod {
    int nd;
    Nod *next;
};

Nod *G[nmax];

void getData(Nod *G[nmax],int &n,int &m,int &source) {
    Nod *p;
    ifstream r("bfs.in");
    r>>n>>m>>source;
    for (int k=1;k<=m;k++) {
        int i,j;
        r>>i>>j;
        p=new Nod;
        p->next=G[i];
        p->nd=j;
        G[i]=p;
    }
    r.close();
}

void detDmin(Nod *G[nmax],int (&d)[nmax],bool (&viz)[nmax],int n,int start) {
    queue <int>Q;
    Nod *p;

    for (int i=1;i<=n;i++) {
        viz[i]=false;
        d[i]=0;
    }
    viz[start]=true;
    Q.push(start);
    while (!Q.empty()) {
        int prec=Q.front();
        Q.pop();
        p=G[prec];
        while (p) {
            if (!viz[p->nd]) {
                viz[p->nd]=true;
                d[p->nd]=d[prec]+1;
                Q.push(p->nd);
            }
            p=p->next;
        }
    }
}

void printDmin(int (&d)[nmax],bool (&viz)[nmax],int n) {

    ofstream w("bfs.out");
    for (int i=1;i<=n;i++)
        if (viz[i])
            w<<d[i]<<" ";
        else
            w<<"-1"<<" ";
        w.close();
}

void printVec(Nod *G[nmax],int n) {

    for (int i=1;i<=n;i++) {
        cout<<i<<":";
        Nod *p=G[i];
        while (p) {
            cout<<p->nd<<" ";
            p=p->next;
        }
        cout<<"\n";
    }
}

int main() {
    int n,m,source,d[nmax];
    bool viz[nmax];

    getData(G,n,m,source);
    detDmin(G,d,viz,n,source);
    printDmin(d,viz,n);
    // printVec(G,n);
    return 0;
}