#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream in("bfs.in");
ofstream out("bfs.out");

int n, m, s, level[100001];
queue <int> q;
vector <int> vertex[100001];

void initialise()
{
  int i;
  for(i=1; i<=n; i++)
    level[i]=-1;
}

void bfs(int current)
{ 
  int next, i;
  q.push(current);
  level[current] = 0;

  while(!q.empty())
  {
    current = q.front();
    q.pop();
    
    for(i=0; i<vertex[current].size(); i++)
    {
      next = vertex[current][i];
      if(level[next] < 0)
      {
        level[next] = level[current] + 1;
        q.push(next);
      }
    }
  }
}

int main()
{
  int i, x, y;
  in>>n>>m>>s;

  for(i=1;i<=m;i++)
  {
    in>>x>>y;
    vertex[x].push_back(y);
    //vertex[y].push_back(x);
    out<<x<<" "<<y<<"\n";
  }

  initialise();

  bfs(s);

  for(i=1; i<=n; i++)
    out<<level[i]<<" ";
  return 0;
}