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

using namespace std;

int n, m, start;
int n1, n2, current;
vector<vector<int>> graph(100002);
vector<int> distances(100002, -1);
queue<int> to_visit;

void bfs() {
  to_visit.push(start);
  while(!to_visit.empty()) {
    current = to_visit.front();
    to_visit.pop();
    for(auto pnext: graph[current]) {
      if(distances[pnext] == -1) {
        distances[pnext] = distances[current] + 1;
        to_visit.push(pnext);
      }
    }
  }
}

int main()
{
    graph.resize(100001);

    ifstream fin("bfs.in");
    fin >> n >> m >> start;
    for(int i = 0; i < m; i++) {
      fin >> n1 >> n2;
      graph[n1].push_back(n2);
    }
    fin.close();

    distances[start] = 0;
    bfs();

    ofstream fout("bfs.out");
    for(int i = 1; i <= n; i++) {
      fout << distances[i] << " ";
    }
    fout.close();

    return 0;
}