#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
vector <int> v[DIMN];
deque <int> dq;
int f[DIMN] , dist[DIMN];
int main()
{
    FILE *fin = fopen ("bfs.in" , "r");
    FILE *fout = fopen ("bfs.out" , "w");
    int n , m , s , i , x , y ,nod , vecin;
    fscanf (fin,"%d%d%d",&n,&m,&s);
    for (i = 1 ; i <= m ; i++){
        fscanf (fin,"%d%d",&x,&y);
        v[x].push_back(y);
    }

    /// presupun ca toate nodurile sunt inaccesibile la inceput
    for (i = 1 ; i <= n ; i++)
        dist[i] = -1;

    /// dist[x] = distanta minima de la x la s

    dist[s] = 0;
    f[s] = 1;
    dq.push_back(s);

    while (!dq.empty()){

        nod = dq.front();
        dq.pop_front();
        /// evaluam nodul 'nod' care se afla la distanta
        /// dist[nod] fata de nodul sursa

        for (i = 0 ; i < v[nod].size() ; i++){
            vecin = v[nod][i];

            if (f[vecin] == 0){
                /// nu am mai ajuns pana acum in nodul vecin
                /// il putem adauga in deque

                //printf ("Am ajuns in nodul %d din nodul %d, pozitionandu-l pe nivelul %d\n", vecin , nod , 1 + dist[nod]);

                f[vecin] = 1;
                dist[vecin] = 1 + dist[nod];
                dq.push_back(vecin);

            }
        }

    }

    for (i = 1 ; i <= n ; i++)
        fprintf (fout,"%d ",dist[i]);

    return 0;
}