#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstring>

using namespace std;

long long N, M, S, A, B, i;

vector<int> V[100010];

int DIST[100010];

void solve()
{

    queue<int> Q;

    Q.push(S);

for(i=1;i<=N;++i)
    DIST[i] = -1;
    DIST[S] = 0;

    while(!Q.empty())
    {
        int now = Q.front();

        for(vector<int>::iterator it=V[now].begin();it!=V[now].end();++it)
        {

            if(DIST[*it] == -1)
            {
                DIST[*it] = DIST[now] + 1;
                Q.push(*it);
            }
        }

        Q.pop();

    }
}

int main()
{

    freopen("bfs.in", "r", stdin);
    freopen("bfs.out", "w", stdout);

    cin>>N>>M>>S;

    for(i=1;i<=M;++i)
    {
        int A, B;
        scanf("%d %d", &A, &B);
        V[A].push_back(B);
    }

    solve();

    for(i=1;i<=N;++i)
        cout<<DIST[i]<<" ";

    return 0;
}