#include <iostream>
#include <fstream>
#include <queue>
#define nmax 100005
using namespace std;

ifstream in("bfs.in");
ofstream out("bfs.out");

int n, m, start, cost[nmax];
vector<int> v[nmax];
queue<int> s;

void citeste()
{ int x, y;

    in>>n>>m>>start;
    for (int i=1; i<=m; ++i)
     {
         in>>x>>y;
         v[x].push_back(y);
     }

}

void bfs(int nod)
{
    cost[nod] = 0;
    s.push(nod);

    while ( !s.empty() )
     {
         for ( unsigned i = 0; i < v[s.front()].size(); ++i )
          {
              if ( cost[ v[ s.front() ][i] ] == -1 )
               {
                   cost[ v[ s.front() ][i] ] = cost[ s.front() ] + 1;
                   s.push( v[ s.front() ][i] );
               }
              else
               cost[ v[ s.front() ][i] ] = min( cost[ v[ s.front() ][i] ], cost[ s.front() ] + 1 );
          }
         s.pop();
     }

}

int main()
{
    citeste();

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

    bfs(start);

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

return 0;
}