#include <bits/stdc++.h>

using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

#define Nmax 100009

int n, m, s, viz[Nmax], Q[Nmax], a, b;
vector <int> L[Nmax];

int main()
{
    fin>>n>>m>>s;

    for(int i = 0; i<m; i++)
    {
        fin>>a>>b;
        L[a].push_back(b);
    }

    Q[1]=s; viz[s]=1;
    int p=1,u=1;

    while(p<=u)
    {
        int i=Q[p++],sf=L[i].size();
        for(int j = 0; j<sf; j++)
        {
            if(viz[L[i][j]] == 0)
            {
                viz[L[i][j]]=viz[i]+1;
                Q[++u]=L[i][j];
            }
        }
    }

    for(int i = 1; i<=n; i++)
    {
        fout<<viz[i]-1<<" ";
    }

    return 0;
}