#include <stdio.h>
#include <stdlib.h>
FILE *f, *g;
int n, m, s, viz[100000];
struct nod
{
    short val;
    struct nod *urm;
}*ultim, *q, *lista[100000], *coadaP, *coadaU,*p;

void citire_lista()
{
    int x, y;
    while ((fscanf(f, "%d%d", &x, &y)) != EOF)
        if (!lista[x])
        {
            lista[x] = (struct nod*)malloc((sizeof(lista[x])));
            lista[x]->val = y;
            lista[x]->urm=0;
            ultim = lista[x];
        }
        else
        {
            q = (struct nod*)malloc((sizeof(lista[x])));
            q->val = y;
            q->urm = lista[x];
            lista[x] = q;

        }
}
void afisare_lista()
{
    int i;
    for (i=1; i<=n; i++)
    {
        q=lista[i];
        printf("%d: ", i);
        while (q)
        {
            printf("%d ", q->val);
            q = q->urm;
        }
        printf("\n");
    }
}
struct nod *creeare_nod(short val)
{
    struct nod *nodNou = (struct nod*)malloc(sizeof(nodNou));
    nodNou->val = val;
    nodNou->urm = 0;
    return nodNou;
}
void BFS()
{
    int k=1;
    viz[s] = k++;
    coadaP = creeare_nod(s);
    coadaU = coadaP;
    while(coadaP)
    {
        q = lista[coadaP->val];
        while(q)
        {
            if (viz[q->val] == 0)
            {
                viz[q->val] = k;
                p = creeare_nod(q->val);
                coadaU->urm = p;
                coadaU = p;
            }
            q = q->urm;
        }
        k++;
        p = coadaP;
        coadaP = coadaP->urm;
        free(p);
    }
}

int main()
{
    f = fopen("bfs.in", "r");
    g = fopen("bfs.out", "w");
    int i, j;

    fscanf(f, "%d%d%d", &n, &m, &s);
    citire_lista();
    //afisare_lista();
    //printf("\n%d %d %d", n, m, s);
    BFS();
    for (i=1; i<=n; i++)
        fprintf(g, "%d ", viz[i]-1);
    return 0;
}