#include <fstream>
#include <queue>
#include <vector>
using namespace std;

int n,m,s;
vector <pair<int,int> > edges[100005];
int dist[100005]; // distanta de la s la celelalte noduri

void initArray(int v[100005], int value,int lastInitElement)
{
  for (int i=0; i<=lastInitElement+1; i++)
  {
    v[i]=value;
  }
}

void read()
{
  ifstream d("bfs.in");
  d>>n>>m>>s;

  //vector <pair <int,int> >::iterator it;
  int x,y;

  for (int i=1; i<=m; i++)
  {
    d>>x>>y;
    edges[x].push_back(make_pair(x,y));
  }
}

void bfs(int d[100005])
{
  queue<int> q;
  vector <pair<int,int> >::iterator it;

  d[s]=0;
  q.push(s);
  while (!q.empty())
  {
    int vertex=q.front();
    q.pop();
    for (it=edges[vertex].begin(); it!=edges[vertex].end(); it++)
    {
      if (d[(*it).second]==-1)
      {
        d[(*it).second]=d[vertex]+1;
        q.push((*it).second);
      }
    }
  }
}

void scrie(int v[100005])
{
  ofstream o("bfs.out");
  for (int i=1; i<=n;i++)
  {
    o<<v[i]<<' ';
  }
}

int main()
{
  read();
  initArray(dist,-1,n);
  bfs(dist);
  scrie(dist);
}