#include <bits/stdc++.h>

using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
int N,M,S;
int dp[100005];
const int INF = 2000000000;
vector < int > L[100005];
queue < int > Q;
inline void Read()
{
    int i,x,y;
    fin>>N>>M>>S;
    for(i = 1; i <= M; i++)
    {
        fin>>x>>y;
        L[x].push_back(y);
    }
    for(i = 1; i <= N; i++) dp[i] = INF;
    dp[S] = 0;
}

void BFS(int nod)
{
    int i;
    Q.push(nod);
    while(!Q.empty())
    {
        nod = Q.front();
        Q.pop();
        for(i = 0 ; i < L[nod].size(); i++)
            if(dp[L[nod][i]] == INF)
        {
            dp[L[nod][i]] = dp[nod]+1;
            Q.push(L[nod][i]);
        }
    }
}
inline void Output()
{
    int i;
    for(i = 1; i <= N; i++)
        if(dp[i] == INF) fout<<"-1 ";
        else fout<<dp[i]<<" ";
    fout<<"\n";
    fout.close();
}

int main()
{
    Read();
    BFS(S);
    Output();
    return 0;
}