#include <fstream>
#include <cstring>
#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;

    memset (viz, false, sizeof(viz));
    memset (d, 0, sizeof(d));

    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();
}

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);
    return 0;
}