#include <iostream>  //Distanta minima de la nodul S la celelalte
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");
/*Exemple:
5 7 2
1 2
2 1
2 2
3 2
2 5
5 3
4 5

*/

//NUMEROTARE DE LA 1 la n
void Citire(vector<int> V[], int &n, int &m, int &S)
{
   //Citirea grafului orientat, vecinii
   f>>n>>m>>S;
   for(int i = 0; i < m; i++)
   {
      int x,y;
      f>>x>>y;
      V[x].push_back(y);//Adaugam vecinii lui x
   }
}

void A(deque<int> d)
{
   //Afiseaza ce este in coada d
   deque<int>::iterator it;
   for( it=d.begin(); it!=d.end(); it++)
      cout<<*it<<" ";
   cout<<endl;
}

int viz[100010] = {0};
deque<int> coada;

void BFS(vector<int> V[], int n, int m, int S)
{
   //Parcurgere in latime de la S la celelalte noduri (recursiv)
   //A(coada);
   if(coada.empty()) return;

   for(int i = 0; i < V[S].size(); i++)
   {
      //V[S][i] vecinul lui S

      if(!viz[V[S][i]] && V[S][i]!=S)
      {

         //Nu a fost vizitat inca
         coada.push_front(V[S][i]);
         viz[V[S][i]] = viz[S] + 1;
      }
   }

   coada.pop_back();

   BFS(V,n,m,coada.back());
}

int main()
{
   int n,m,S;
   vector<int> V[100000];
   Citire(V,n,m,S);

   coada.push_back(S);
   BFS(V,n,m,S);

   for(int i=1; i<=n; i++)
   {
      if(i==S)g<<"0 ";
      else if(viz[i]==0) g<<"-1 ";
      else g<<viz[i]<<" ";
   }

   return 0;
   for(int i=1;i<=n;i++)
   {
      cout<<i<<" : ";
      for(int j=0;j<V[i].size();j++)
         cout<<V[i][j]<<" ";
      cout<<endl;
   }
}