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

using namespace std;

int N, M, S;

void show(vector<int> DMIN)
{
    for(vector<int>::iterator it=DMIN.begin()+1;it!=DMIN.end();++it)
        cout<<(*it == 99999 ? -1 : *it)<<" ";
    cout<<"\n";
}

void solve(vector<vector<pair<int, int> > > &V, vector<int> &DMIN)
{

    queue<int> Q;

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

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

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

                DMIN[it->first] = DMIN[now] + it->second;

                Q.push(it->first);

            }

        Q.pop();
    }
}

int main()
{

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

    scanf("%d %d %d", &N, &M, &S);

    vector<vector<pair<int, int> > > V(N+1, vector<pair<int, int> >());

    vector<int> DMIN(N+1, 99999);

    for(int i=1;i<=M;++i)
    {
        int X, Y;
        scanf("%d %d", &X, &Y);
        V[X].push_back(make_pair(Y, 1));
    }
/*
    for(vector<vector<pair<int, int> > >::iterator it=V.begin();it!=V.end();++it)
    {
        for(vector<pair<int, int> >::iterator it2=(*it).begin();it2!=(*it).end();++it2)
            cout<<it2->first<<","<<it2->second<<" ";
        cout<<"\n";
    }*/

    solve(V, DMIN);

    show(DMIN);

    return 0;
}