#include <iostream>
#include <deque>
#include <fstream>
#include <time.h>

using namespace std;

int n,m,*v,*d;

class nod {
    int info;
    nod *next,*last;
public:
    nod() {
    }
    nod (int x) {
        info = x;
        next = NULL;
        last = NULL;
    }
    nod* getNext() {
        return next;
    }
    void setNext(nod *p) {
        next = p;
    }
    nod* getLast() {
        return last;
    }
    void setLast(nod* p) {
        last = p;
    }
    int getInfo() {
        return info;
    }
};

nod **nodes;

void bfs (int x) {
    deque<int> s;
    s.push_front(x);
    v[x] = 1;
    d[x] = 0;
    int c = 1,nr = 0,c1 = 1;
    while (!s.empty()) {
        c1--;
        int e = s.front();
        s.pop_front();
        if (e < 0) {
            c1 = -e;
            nr = 0;
            continue;
        }
        if (!e) break;
        nod* q = nodes[e];
        while (q) {
            int en = q->getInfo();
            if (!v[en]) {
                v[en] = 1;
                nr++;
                d[en] = c;
                s.push_back(en);
            }
            q = q->getNext();
        }
        if (!c1) {
            s.push_front(-nr);
            c++;
        }
    }
}

void addnod(nod* &p,int x) {
    if (!p) {
        p = new nod(x);
        p->setLast(p);
    }
    else {
        nod* q = new nod(x);
        p->getLast()->setNext(q);
        p->setLast(q);
    }
}

int checkv() {
    int i;
    for (i=1;i<=n;i++) if (!v[i]) return 0;
    return 1;
}
int main()
{
    int s;
    ifstream f("bfs.in");
    f>>n>>m>>s;
    v = new int[n+1];
    d = new int[n+1];
    int i,x,y;
    nodes = new nod*[n+1];
    for (i=1;i<=n;i++) {
        v[i] = 0;
        d[i] = -1;
        nodes[i] = NULL;
    }
    while (f>>x>>y) addnod(nodes[x],y);
    f.close();
    cout<<(float)clock()/CLOCKS_PER_SEC;
    bfs(s);
    ofstream g("bfs.out");
    for (i=1;i<=n;i++) g<<d[i]<<" ";
    g.close();
    cout<<endl<<(float)clock()/CLOCKS_PER_SEC;
    return 0;
}