#include<cstdio>
#include<vector>
#include<queue>
#define NMAX 100100

using namespace std;

vector<int> L[NMAX];
int cst[NMAX];
queue<int> Q;

int main()
{
    int N,M,start,i,now,x,y;
    vector<int> :: iterator it;

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

    scanf("%d%d%d",&N,&M,&start);
    for(i=1;i<=M;i++)
    {
        scanf("%d%d",&x,&y);
        L[x].push_back(y);
    }

    for(i=1;i<=N;i++)
        cst[i] = -1;
    cst[start]=0; Q.push(start);

    while(!Q.empty())
    {
        now = Q.front();
        for(it = L[now].begin() ; it != L[now].end(); it ++)
            if (cst[*it] == -1)
            {
                cst[*it] = cst[now] + 1;
                Q.push(*it);
            }
        Q.pop();
    }

    for(i=1;i<=N;i++)
        printf("%d ",cst[i]);
    return 0;
}