Program cautarea_afisarea_celui_mai_scurt_drum_in_graf;

 type graf=record
          x,y:integer;
           end;
      rezultate=record
       x,k:integer;
          end;

var i,j,n,m,s,l,r:integer;
        drum:array[1..1000000] of graf;
        rez:array[1..100001] of rezultate;
        parcurs:array[1..100001] of boolean;
        val:array[1..100000] of longint;

    Procedure readfile;
     var f:text;
      begin
       assign(f,'bfs.in'); reset(f);
        readln(f,n,m,s);
        for i:=1 to m do
           readln(f,drum[i].x,drum[i].y);
        close(f);
     end;





    begin

      readfile;
          for i:=1 to n do
          parcurs[i]:=true;

       l:=1; r:=2;
         rez[l].x:=s; rez[l].k:=1; parcurs[s]:=false; val[s]:=1;
       while (l<r) do
        begin
          for i:=1 to m do
            if (drum[i].x=rez[l].x) and (parcurs[drum[i].y]) then
                     begin
                      val[drum[i].y]:=rez[l].k+1;
                      parcurs[drum[i].y]:=false;
                      rez[r].x:=drum[i].y;
                      rez[r].k:=rez[l].k+1;
                      inc(r);
                     end;
          inc(l);
        end;

    for i:=1 to n do
      if (val[i]-1<0) then write('-1 ') else write(val[i]-1,' ');

    end.