#include <iostream>
#include <fstream>
using namespace std;

int viz[100], c[100], arc[100], a[100][100];

int main()
{
   int p, u, i, j, n, m, sursa, x, y, s = 0, ok = 0;
   ifstream f("bfs.in");
   ofstream g("bfs.out");
   f>>n>>m>>sursa;
   int copie = m;
   while ( copie != 0)
   {
       f>>x>>y;
       a[x][y]=1;
       copie--;
   }

   p = u =1;
   c[1] = sursa;
   viz[sursa] = 1;
   while(p <= u)
   {
       i = c[p];
       p++;

       for(j=1; j<=n; j++)
       {
          if(a[i][j] == 1 && viz[j] == 0)
       {
         u++;
         c[u] = j;
         viz[j] = 1;
         arc[j] = s + 1;
         ok++;
         cout<<arc[j]<<endl;
       }


       }

       if( ok != 0)
       {
           s++;
           ok = 0;
       }


   }


   for (i = 1; i <=n; i++)
     {if( i == sursa)
          arc[i]= 0;
      if( arc[i]==0 && i != sursa)
         arc[i] = -1;
     }

  for (i = 1; i <=n; i++)
     g<<arc[i]<<" ";



    return 0;
}