#include <cstdio>
#include <fstream>
#include <vector>
#include <deque>
#include <iostream>

using namespace std;

int n, m, s;
vector<int> result;
deque<int> queue;
vector<vector<int>> edges;

void bfs() {
  int count = 0;
  result[s] = count;
  queue.push_back(s);
  int curr;
  while(!queue.empty()) {
    curr = queue.front();
    queue.pop_front();
    for(int i = 0; i < edges[curr].size(); i++) {
      int dest = edges[curr][i];
      if(result[dest] == -1) {
        queue.push_back(dest);
        result[dest] = ++count;
      }
    }
  } 
}
  
int main() {
  ifstream f("bfs.in");
  ofstream g("bfs.out");
  f >> n >> m >> s;
  int fst, snd;  

  for(int i = 1; i <= m; i++) {
    f >> fst >> snd;
    edges[fst].push_back(snd);
    result[i] = -1;
  }
  
  bfs();
  for(int i = 1; i <= m; i++) {
    g << result[i] << " ";
  }

  return 0;
}