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

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

        for(int i = 1; i <= n;i ++)
        {
            if( matrix[c.front()][i] == 1 && visited[i] == false)
            {

                paths[i] = paths[c.front()] + 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 <vector <int>> matrix(n+1,vector <int>(n+1));

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

        int x,y;
        fin >> x >> y;
        matrix[x][y] = 1;

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

    }*/
    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, matrix,visited,paths,n);

    return 0;
}