#include <fstream>
#include <iostream>
#define nmax 100005
#include <vector>

using namespace std;

int n,m,s,D[nmax],nr[nmax],C[nmax];

vector<int>Q[nmax];

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

void Create()
{
    int i;
    for(i=0;i<nmax;i++)
        D[i]=-1;
}

void Citire()
{
    int i,x,y,j;

    fin>>n>>m>>s;

    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        Q[x].push_back(y);
    }
    for(i=1;i<=n;i++)
        nr[i] = Q[i].size();
}

int main()
{
    int k,i,j;
    Citire();
    Create();

    C[1] = s;
    k=1;
    D[s]=0;

    for(i=1;i<=k;i++)
        for(j = 0; j < nr[C[i]]; j++)
            if(D[Q[C[i]][j]]==-1)
            {
                C[++k] = Q[C[i]][j];
                D[C[k]] = D[C[i]] + 1;
            }

    for(i=1;i<=n;i++)
        fout << D[i]<<' ';
    return 0;
}