Program Bfs;
{ Breadth-first search * Parcurgere in latime }
type Stiva=^Nod;
     Nod=record
       x : longint;
       next : Stiva;
     end;
var n,m,s,i,x,y,g,cp,cu : longint;
    q,ca : array[1..100001] of longint;
    V : array[1..100000] of Stiva;
    f : text;
    W : Stiva;

begin
  assign(f,'bfs.in');
  reset(f);
  readln(f,n,m,s);
  for i:=1 to n do begin
    q[i]:=-1;
    V[i]:=nil;
  end;
  for i:=1 to m do begin
    readln(f,x,y);
    new(W);
    W^.x:=y;
    W^.next:=V[x];
    V[x]:=W;
  end;
  close(f);

  cp:=1;
  cu:=1;
  ca[1]:=s;
  q[s]:=0;
  while cp<=cu do begin
    x:=ca[cp];
    cp:=cp+1;
    g:=q[x]+1;
    while V[x]<>nil do begin
      y:=V[x]^.x;
      W:=V[x];
      V[x]:=V[x]^.next;
      {dispose(W);}
      if q[y]=-1 then begin
        q[y]:=g;
        cu:=cu+1;
        ca[cu]:=y;
      end;
    end;
  end;

  assign(f,'bfs.out');
  rewrite(f);
  for i:=1 to n do write(f,q[i],' ');
  close(f);
end.