#include <fstream>
#include <algorithm>

using namespace std;

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

int v[2][1000001], start[1000001], c[1000001], nod[100001];
bool viza[100001];
int n, m, x, y, k=0, S;

void citire()
{
    in>>n>>m>>S;
    for(int i=1; i<=m; i++)
    {
        in>>x>>y;
        k++;
        v[0][k]=y;
        v[1][k]=start[x];
        start[x]=k;
    }
}

int main()
{
    citire();

    for(int i=1; i<=n; i++)
        nod[i]=-1;

    int st=1, dr=1, man, k=0, k1=1;
    c[1]=S;
    viza[S]=1;
    nod[S]=k;
    while(st<=dr)
    {
        man=start[c[st]];
        while(man)
        {
            if(viza[v[0][man]]==0)
            {
                c[++dr]=v[0][man];
                viza[v[0][man]]=1;
                nod[v[0][man]]=k+1;
            }
            man=v[1][man];
        }
        if(st==k1)
        {
            k++;
            k1=dr;
        }
        st++;
    }
    for(int i=1; i<=n; i++)
        out<<nod[i]<<" ";
    return 0;
}