#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");
int main()
{

    int s,n,m;

    f>>n>>m>>s;

  vector<  vector <int> >L (n+1);

    vector <bool> vis (n+1,0);

    vector <int> dist (n+1,-1);

    queue <int> Q;



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

        int x,y;

        f>>x>>y;

        L[x].push_back(y);



    }

    Q.push(s);

    dist[s] = 0;

    vis[s] = true;

    while(!Q.empty())

    {

        int p = Q.front();

        Q.pop();

        for( unsigned int i = 0; i < L[p].size();i++)

        {

            if(!vis[L[p][i]])

            {   vis[L[p][i]] = true;

                Q.push(L[p][i]);

                dist[L[p][i]] = dist[p] + 1;



            }

        }

    }



    for(int i = 1;i<=n;i++){

        g<<dist[i]<<" ";

    }





    return 0;

}