#include<cstdio>
#include<fstream>
#include<iostream>
#include<vector>
#include<ctime>
#include<cstdlib>
#define MAX 100005
using namespace std;

vector <int> d,G[MAX];
int n;

void bfs(int sursa)
{
    vector<int> coada;
    int st,dr;
    coada.push_back(sursa);
    d[sursa]=0;
    st=dr=0;
    while(st<=dr)
    {
        int k=coada[st++];
        for(int i=1;i<G[k].size();i++)
            {

                int vecin=G[k][i];
                if(d[vecin]==-1 || d[vecin]>d[k]+1)
                {
                    d[vecin]=d[k]+1;
                    coada.push_back(vecin);
                    dr++;
                }
            }
    }
}

void dfs(int varf)
{
    for(int i=1;i<G[varf].size();i++)
    {
        int vecin=G[varf][i];
        if(d[vecin]==-1 || d[vecin]>d[varf]+1)
        {
            d[vecin]=d[varf]+1;
            dfs(vecin);
        }
    }
}

int main()
{
    int m,s,i,j;
    ifstream fin("bfs.in");
    freopen("bfs.out","w",stdout);
    fin>>n>>m>>s;
    d.assign(n+1,-1);
    for(i=1;i<=n;i++)
        G[i].push_back(0);
    for(i=1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        G[x].push_back(y);
    }
    srand(time(NULL));
    d[s]=0;
    int ce=rand()%2;
    if(ce==1)
        bfs(s);
    else
        bfs(s);
    for(i=1;i<=n;i++)
        printf("%d ", d[i]);
    return 0;
}