#include <fstream>

using namespace std;

ifstream f("bfs.in");
ofstream g("bfs.out");

int i,j,n,v[10001][10001],viz[100001],m,s,x,y,Q[10001],l,e,p;

int main()
{
    f>>n>>m>>s;
    for(i=1;i<=m;i++)
        {
            f>>x>>y;
            v[x][0]++;
            v[x][v[x][0]]=y;
        }

    Q[1]=s;
    p=1;
    l=1;
    viz[s]=1;
    while(p<=l)
    {
        e=Q[p];
        for(i=1;i<=v[e][0];i++)
        if(viz[v[e][i]]==0)
        {
            l++;
            Q[l]=v[e][i];
            viz[Q[l]]=viz[Q[p]]+1;
        }
        p++;
    }

    for(i=1;i<=n;i++)
        g<<viz[i]-1<<" ";

    return 0;
}