#include <iostream>
#include <deque>
#include <list>
#include <fstream>
#include <vector>
#include <typeinfo>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
void bfs(int start, deque <int> c, vector < list<int>> ad,vector <bool> visited, vector<int> paths,int n)
{

    while(c.size() >= 1)
    {

        int parent =   c.front();
        for(auto it=ad[parent].begin();it!=ad[parent].end();it++)
        {
            int i =*it;
            if( visited[i] == false)
            {

                paths[i] = paths[parent] + 1;
                visited[i] = true;
                c.push_back(i);


            }

        }
         c.pop_front();


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


}



int main()
{
    int n,m,start;
    fin>>n>>m>>start;
    vector <list <int>> ad(n+1);

    for(int i = 0; i < m; i ++)
    {

        int x,y;
        fin >> x >> y;
        ad[x].push_back(y);

    }
    /*for(auto s=ad.begin();s!=ad.end();s ++)
    {
        for(auto ss = s->begin();ss != s->end(); ss++)
            cout<<*ss<<" ";
        cout<<"\n";

    }*/
    vector <bool> visited (n+1,0);
    vector <int> paths(n+1,-1);
    visited[start] = true;
    paths[start] = 0;
    deque <int> c;
    c.push_back(start);
    bfs(start,c, ad,visited,paths,n);

    return 0;
}