#include <fstream>
#include <string.h>

using namespace std;

struct point{
    int inf;
    point *leg;
};
point *pt,*l[100010];
int n,m,s,x,y,p,u,q[100010],drum[100010],nod;
bool sel[100010];

void bfs()
{
    while (p<=u)
    {
        nod=q[p];
        while(l[nod])
            if(sel[l[nod]->inf]==false)
            {
                u++;
                q[u]=l[nod]->inf;
                sel[l[nod]->inf]=true;
                drum[l[nod]->inf]=drum[nod]+1;
                l[nod]=l[nod]->leg;
            }
            else
                l[nod]=l[nod]->leg;
                p++;
    }
}


int main()
{
    int i,j;
    ifstream f("bfs.in");
    ofstream g("bfs.out");
    memset(l,NULL,sizeof(l));
    f>>n>>m>>s;
    for(i=1;i<=m;i++)
    {
        pt=new point;
        f>>x>>y;
        pt->inf=y;
        pt->leg=l[x];
        l[x]=pt;
    }
    p=u=1;
    q[p]=s;
    sel[s]=true;
    memset(drum,-1,sizeof(drum));
    drum[s]=0;
    bfs();
    for(i=1;i<=n;i++)
        g<<drum[i]<<" ";

    return 0;
}