#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#define maxn 100010

ifstream f("bfs.in");
ofstream g("bfs.out");
vector<int> A[maxn];

int main()
{
    int coada[maxn];
    int n,m,x,y,nStart;
    int prim,ultim,ultimmm,cnt =0;

    f>>n>>m>>nStart;

    int cost[n+1];
    int viz[n+1];

    for(int i=0; i<m; i++)
    {
        f>>x>>y;
        A[x].push_back(y);
    }

    for(int i=0; i<=n;i++)
        {cost[i]=-1;
         viz[i]=0;}

    coada[1]=nStart;
    cost[nStart] = 0;
    viz[nStart] = 1;
    prim=1; ultim=1; ultimmm=ultim+1;

while( prim<=ultim )
{
    for(int i=prim; i<=ultim; i++)
    {
        if(cost[coada[i]] == -1)
            cost[ coada[i] ] = cnt;
        for(int j=0; j<A[ coada[i] ].size(); j++ )
        {
            if( viz[ A[ coada[i] ][j] ] == 0 )
            {viz[ A[ coada[i] ][j] ] = 1;
            coada[ultimmm]=A[ coada[i] ][j];
            ultimmm++;}
        }
    }
    ultim++;
    prim=ultim;
    ultim=ultimmm-1;
    cnt++;
}

    for(int i=1;i<=n;i++)
        g<<cost[i]<<" ";
}