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

using namespace std;

int n,m,*v,*d;

class nod {
    int info;
    nod *next;
public:
    nod() {
        next = NULL;
    }
    nod (int x) {
        info = x;
        next = NULL;
    }
    nod* getNext() {
        return next;
    }
    void setNext(nod *p) {
        next = 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;
        }
        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);
    else {
        nod *q = p;
        while (q->getNext()) q = q->getNext();
        q->setNext(new nod(x));
    }
}

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();
    bfs(s);
    ofstream g("bfs.out");
    for (i=1;i<=n;i++) g<<d[i]<<" ";
    g.close();
    return 0;
}