#include <fstream>
#include <stdint.h>
using namespace std;
fstream f1("bfs.in", ios::in);
fstream f2("bfs.out", ios::out);
///ai un graf orientat cu n varfuri si m arce
///Fiind dat un nod S, sa se determine
/// pentru fiecare nod X, numarul minim de arce ce trebuie parcurse pentru a ajunge din nodul sursa S la nodul X
///faci o parcurgere in latime memo in vect pas[] nr de arce necesare, pt fiecare nod
///faci memo folosind o lista de adiacenta v si vect cap
int32_t n, m,  v[1000001], cap[100001], viz[100001], rad, pas[100001], coada[100001], prim=1, ultim=1, k=1;
struct muchie
{
    int x, y;
}mu[1000001];
void bfs(int x)
{
    while(k!=0)
    {
        ///iei pe rand fii nevizitati ai lui x si ii bagi in coada
        ///punandu-le pasul
        int32_t i;
        for(i=cap[coada[prim]]; i<cap[coada[prim]+1]; i++)
            if(!viz[v[i]])
        {
            viz[v[i]]=1;
            pas[v[i]]=pas[coada[prim]]+1;///pasul tatalui +1
            ultim++;
            k++;
            coada[ultim]=v[i];
        }
        ///elimini nodul tata
        prim++;
        k--;
    }
}
int main()
{
    int32_t i, x, y;
    f1>>n>>m>>rad;
    for(i=1; i<=m; i++)
    {
        f1>>x>>y;
        mu[i].x=x;
        mu[i].y=y;
        ///pas[i] memo provizoriu numarul de fii ai lui i
        pas[x]++;
    }
    cap[1]=1;
    for(i=1; i<=n; i++)
        {
         cap[i+1]=cap[i]+pas[i];
         pas[i]=cap[i];
        }
   pas[1]=1;
   for(i=1; i<=m; i++)
   {
      x=mu[i].x;
      y=mu[i].y;
      v[pas[x]]=y;
      pas[x]++;
   }
   ///ai creat lista de adiacenta
   for(i=1; i<=n; i++)
    pas[i]=0;
   ///faci bfs-ul
   viz[rad]=1;
   coada[prim]=rad;
   bfs(rad);
   for(i=1; i<=n; i++)
      if(viz[i]) f2<<pas[i]<<" ";
      else f2<<-1<<" ";
    return 0;
}