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

using namespace std;

long long N, M, S;

vector<pair<int, int> > MAT[100010];

int DMIN[100010];

void solve()
{
    bool inQ[100010];
    queue<int> Q;

    memset(DMIN, 0x3f3f3f3f, sizeof(DMIN));
    memset(inQ, false, sizeof(inQ));

    DMIN[S] = 0;
    Q.push(S);
    inQ[S] = true;

    while(!Q.empty())
    {
        int now = Q.front();
        Q.pop();
        inQ[now] = false;

        for(vector<pair<int, int> >::iterator it = MAT[now].begin();it != MAT[now].end();++it)
            if(DMIN[now] + it->second < DMIN[it->first])
            {
                DMIN[it->first] = DMIN[now] + it->second;
                if(!inQ[it->first])
                {
                    Q.push(it->first);
                    inQ[it->first] = true;
                }
            }

    }
}

int main()
{

    int i, A, B, C;

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

    cin>>N>>M>>S;

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

    }

    solve();

    for(i=1;i<=N;++i)
        cout<<(DMIN[i] < 0x3f3f3f3f ? DMIN[i] : -1)<<" ";

    return 0;
}