#include <stdio.h>
#include <vector>
#define dim 100001

using namespace std;
vector <int> a[dim],t;
int v[dim],c[dim],tfirst,tlast;
int n,m,s;

void ini()
{
    int i;
    for (i=0;i<dim;i++)
        c[i]=-1;
}

void bfs()
{
    int i;
    tfirst = 0;
    c[s-1]=0;//cost 0
    t.push_back(s-1); // put him in the tail
    while (tfirst<t.size()) //still have values in tail
    {
        v[t[tfirst]] = 1; //mark as done
        for (i=0;i<a[t[tfirst]].size();i++)
            if (v[a[t[tfirst]][i]]==0) // not done
            {
                c[a[t[tfirst]][i]]=c[t[tfirst]]+1; // calculate cost
                t.push_back(a[t[tfirst]][i]); // add in tail
            }
        tfirst ++;
    }
}

int main()
{
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);
    scanf("%d %d %d",&n,&m,&s);
    int i,x1,x2;
    for (i=0;i<m;i++)
    {
        scanf("%d %d",&x1,&x2);
        a[x1-1].push_back(x2-1);
    }
    ini();
    bfs();
    for (i=0;i<n;i++)
        printf("%d ",c[i]);
    return 0;
}