#include<iostream>
#include<queue>
#include<cstdio>
#include<vector>

using namespace std;

typedef vector< vector<int> > Graph;

int main()
{
  freopen("bfs.in", "r", stdin);
  freopen("bfs.out", "w", stdout);

  int N, M, S, v1, v2;
  scanf("%d %d %d", &N, &M, &S);

  Graph graph(N+1, vector<int>());
  vector<int> result(N+1, -1);
  vector<int> explored(N+1, 0);

  for(int i=0; i< M; i++)
  {
    scanf("%d %d", &v1, &v2);
    graph[v1].push_back(v2);
  }

  queue<int> q;
  q.push(S);
  result[S] = 0;

  while(!q.empty())
  {
    int current = q.front();
    q.pop();
    explored[current] = 1;

    for(int i=0; i<graph[current].size(); i++)
    {
      if(explored[graph[current][i]] == 0)
      {
        if(result[graph[current][i]] == -1)
        {
          result[graph[current][i]] = result[current] + 1;
        }
        q.push(graph[current][i]);
      }
    }
  }

  for(int i=1; i<result.size(); i++)
  {
    printf("%d ", result[i]);
  }

  return 0;
}