#include <cstdio>
#define NMAX 100001

using namespace std;

FILE *f = freopen("bfs.in", "r", stdin);
FILE *g = freopen("bfs.out", "w", stdout);

struct nod{
    int vecin;
    nod *urmator;
};

nod *a[NMAX]; ///vector de pointeri, fiecare element a[i] reprezinta 'capul' listei de vecini ai nodului i
int coada[NMAX], p, u, n, m, s;
int dist[NMAX];
bool viz[NMAX];

void insertBeginning(nod *& head, int val) {
    nod *tmp = new nod;
    tmp -> vecin = val;
    tmp -> urmator = head;
    head = tmp;
}

void afisare(nod *& head) {
    nod *tmp = head;
    while(tmp != NULL) {
        printf("%d ", tmp -> vecin);
        tmp = tmp -> urmator;
    }
}

void bfs(int start) {
    for(int i = 1; i<=n; i++)
        dist[i] = -1;
    viz[start] = true;
    p = u = 1;
    coada[p] = start;
    dist[start] = 0;
    while(p <= u) {
        int node = coada[p];
        nod *head = a[node];
        while(head != NULL) {
            if(!viz[head -> vecin] && dist[head -> vecin] == -1) {
                viz[head -> vecin] = true;
                u ++;
                coada[u] = head -> vecin;
                dist[head -> vecin] = dist[node] + 1;
            }
            head = head -> urmator;
        }
        p ++;
    }
}
void readData() {
    scanf("%d%d%d", &n, &m, &s);
    for(int i = 1; i<=m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        insertBeginning(a[x], y);
    }
}
int main() {
    readData();
    /*for(int i = 1; i<=n; i++) {
        printf("Vecinii nodului %d sunt ", i);
        afisare(a[i]);
        printf("\n");
    }*/
     bfs(s);
    for(int i = 1; i<=n; i++)
        printf("%d ", dist[i]);
    return 0;
}