#include <fstream>
#define NMAX 10002
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];
nod* p[NMAX];
bool viz[NMAX];
int n, m, start, i, nrp[NMAX];
void citire();
void BFS(int);
void inserare(LSI& L, int x, nod* p);
int main()
{
    citire();
    BFS(start);
    /*for(i=1; i<=n; i++)
        if(nrp[i]==0 && i!=start)
            fout<<-1<<' ';
        else
            fout<<nrp[i]<<' ';*/
    return 0;
}

void citire()
{
    int x, y, i;
    fin>>n>>m;
    fin>>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;
    }
}

void BFS(int start)
{
    int C[NMAX], x, prim, ultim;
    nod* q;
    C[0]=start;
    prim=ultim=0;
    viz[start]=1;
    while(prim<=ultim)
    {
        x=C[prim++];
        for(q=L[x]; q; q=q->urm)
            if(!viz[q->vf])
                {
                    viz[q->vf]=1;
                    C[++ultim]=q->vf;
                    nrp[q->vf]=nrp[x]+1;
                }
    }
}

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