#include <fstream>
#define NMAX 100005
#define INF 10000000
using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

struct nod
{
    int vf;
    struct nod* urm;
};

typedef struct nod*  LSI;
LSI L[NMAX]; //aici vom avea pe L[i] vecinii vectorului i; L[i] va indica inceputul listei de adiacenta;
nod* p[NMAX]; //acestia vor indica ultimul nod pus, initial indica null;
bool uz[NMAX];
int d[NMAX];

short int C[NMAX];
int prim, ultim;

int n, m, start;

void initializare();
void citire();
void dfs(int start);
void inserare(LSI& L, int x, nod* p);


void bfs(int start);
int calcullungime(int y);
void initializare();

int main()
{int y;
    citire();
    initializare();
    bfs(start);
    for (y=1; y<=n; y++)
        fout<<calcullungime(y)<<' ';
    return 0;
}

void initializare()
{int i;
    for (i=1; i<=n; i++)
        d[i]=INF;
}

void bfs(int start)
{
    int x;
    nod* p;
    C[0]=start;
    d[start]=0;
    prim=ultim=0;
    uz[start]=1;
    while (prim<=ultim)
        {
         //cat timp coada nu e vida
         x=C[prim];
         prim++; //stergem elementul asta din coada
         //parcurgem vecinii lui x;
        for (p=L[x]; p!=NULL; p=p->urm)
            if (d[p->vf]==INF)
                {
                 d[p->vf]=d[x]+1;
                 ultim++;
                 C[ultim]=p->vf;
                }
        }
}

int calcullungime(int y)
{
    if (d[y]==INF)
        return -1;
    return d[y];
}

void dfs(int x)
{
 nod* p;
 uz[x]=1; //marchez varful in care sunt;
 fout<<x<<' ';
 for (p=L[x]; p!=NULL; p=p->urm)
    if (uz[p->vf]==0)
        dfs(p->vf);
}

void citire()
{int x, y, i;
    fin>>n>>m>>start;
    for (i=1; i<=m; i++)
        {
         fin>>x>>y;
         inserare(L[x], y, p[x]);
         if (p[x]==NULL)
            p[x]=L[x];
            else
            p[x]=p[x]->urm; //adica ne ducem tot la ultimul nod adaugat;
        }
}

void inserare(LSI& L, int x, nod* p)
{
    nod* q = new nod;
    q->vf=x;
    if (p==NULL) //daca introducem la inceputul listei
        {
        q->urm=L;
        L=q;
        }
        else
        {
        q->urm = p->urm;
        p->urm = q;
        }
}