#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

struct nod
{
    int inf;
    nod*a;
}*p[100010];

int n,m,s,a[100010];

int main()
{
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);
    scanf("%d %d %d",&n,&m,&s);
    int x,y;
    for(int i=1; i<=m; i++)
    {
        scanf("%d %d",&x,&y);
        nod*c=new nod;
        c->inf=y;
        c->a=p[x];
        p[x]=c;
    }

    a[s]=1;
    queue<int> k;
    k.push(s);
    while(!k.empty())
    {
        for(nod* c=p[k.front()]; c!=NULL; c=c->a)
            if(a[c->inf]==0)
            {
                a[c->inf]=a[k.front()]+1;
                k.push(c->inf);
            }
        k.pop();
    }
    for(int i=1; i<=n; i++)
        printf("%d ",a[i]-1);
    return 0;
}