#include <bits/stdc++.h>

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

vector <int> V[100005];
queue <int> Q;
int D[100005],n,m,S;
int main()
{

    f>>n>>m>>S;
    for(int i=1; i<=n; i++)
        D[i]=1e9;
    Q.push(S);
    D[S]=0;
    while(m--)
    {
        int x,y;
        f>>x>>y;
        V[x].push_back(y);
    }
    while(!Q.empty())
    {
        int x=Q.front();
        Q.pop();
        for(int i=0; i<V[x].size(); i++)
        {
            if(D[V[x][i]]>D[x]+1)
            {
                D[V[x][i]]=D[x]+1;
                Q.push(V[x][i]);
            }
        }
    }
    for(int i=1; i<=n; i++)
        if(D[i]==1e9)
            g<<-1<<' ';
        else
            g<<D[i]<<' ';
    return 0;
}