#include <iostream>
#include <vector>
#include <queue>
#include <fstream>

using namespace std;

vector <vector <int>> graph;
vector <int> visited;
unsigned int n, m, p, i, x, y;


void BFS(unsigned int vertex)
{
  if(vertex < 0 || vertex > n-1)
    return;
  
  unsigned int element, i;
  queue <int> q;

  q.push(vertex);

  visited[vertex] = 1;
 
  while(!q.empty())
    {
      element = q.front();

      for (i = 0; i < graph[element].size(); i++)
	{
	  if(!visited[graph[element][i]])
	    {
	      q.push(graph[element][i]);
	      visited[graph[element][i]] = visited[element] + 1;

	      
	    }
	  
	}

      q.pop();

    }
}



int main()
{
  ifstream in("bfs.in");
  ofstream out("bfs.out");
  
  in >> n >> m >> p;
  graph.resize(n);
  
  visited.resize(n, false);
  

  for (i = 0; i < m; i++)
    {
      in >> x >> y;

      x--;
      y--;

      graph[x].push_back(y);
    }
  
  p--;
  BFS(p);
  
  
  for (i = 0; i < visited.size(); i++)
      out << visited[i]-1 << " ";      


  
  return 0;
}