#include <iostream>
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

vector<vector<int>> read_date(unsigned & n,unsigned & m, unsigned& nod)
{
    ifstream in("bfs.in");

    in>>n>>m>>nod;

    vector<vector<int>> mat(n+2);
    int x,y;
    for(unsigned i = 0 ; i < m ; i++)
    {
        in>>x>>y;


        mat[x].push_back(y);

    }

    return mat;

}

int main()
{
    unsigned n, m,nod;

    vector<vector<int>> v = read_date(n,m,nod);
    deque < int> deq ;
    vector<bool > viz(n+2,false);
    int cost[n+2];


    int x = nod;

    deq.push_front(x);

   for(unsigned i = 1 ; i<= n ;i++)
         cost[i] = -1;


    cost[x]  = 0 ;
    viz[x] = true;

    while( !deq.empty())
    {
        x = deq.front();

        for(unsigned i = 0 ; i< v[x].size() ;  i++)
                    if(!viz[v[x][i]])
        {
            cost[v[x][i]] = cost[x] + 1;
            viz[v[x][i]] = true;
            deq.push_back(v[x][i]);

        }

        deq.pop_front();


    }

ofstream out("bfs.out");

    for(unsigned i = 1 ; i<= n ;i++)
        out<<cost[i] <<" ";



    return 0;
}