Program Bfs;
{ Breadth-first search * Parcurgere in latime }
type PNod=^Nod;
     Nod=record
       x : longint;
       next : PNod;
     end;
     Stiva=PNod;
     Coada=record
       P,U : PNod;
     end;
var q : array[1..100000] of longint;
    n,m,s : longint;
    V : array[1..100000] of Stiva;
    C : Coada;

procedure AddInSt(var S : Stiva; x : longint);
var W : Stiva;
begin
  new(W);
  W^.x:=x;
  W^.next:=S;
  S:=W;
end;

function ExtractSt(var S : Stiva) : longint;
var W : Stiva;
    rez : longint;
begin
  rez:=S^.x;
  W:=S;
  S:=S^.next;
{  dispose(W);}
  ExtractSt:=rez;
end;

procedure AddInCoada(var C : Coada; x : longint);
var W : Pnod;
begin
  new(W);
  W^.x:=x;
  W^.next:=nil;
  if C.P=nil then begin
    C.P:=W;
    C.U:=W;
  end
  else begin
    C.U^.next:=W;
    C.U:=W;
  end;
end;

function ExtractCoada(var C : Coada) : longint;
var W : PNod;
    rez : longint;
begin
  rez:=C.P^.x;
  W:=C.P;
  C.P:=C.P^.next;
  if C.P=nil then C.U:=nil;
{  dispose(W);}
  ExtractCoada:=rez;
end;

procedure Citeste;
var Intrare : text;
    i,x,y : longint;
begin
  assign(Intrare,'bfs.in');
  reset(Intrare);
  readln(Intrare,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(Intrare,x,y);
    AddInSt(V[x],y);
  end;
  close(Intrare);
end;

procedure Calculeaza;
var g,x,y : longint;
begin
  C.P:=nil;
  C.U:=nil;
  AddInCoada(C,s);
  q[s]:=0;
  while C.P<>nil do begin
    x:=ExtractCoada(C);
    g:=q[x]+1;
    while V[x]<>nil do begin
      y:=ExtractSt(V[x]);
      if q[y]=-1 then begin
        q[y]:=g;
        AddInCoada(C,y);
      end;
    end;
  end;
end;

procedure Scrie;
var Iesire : text;
    i : longint;
begin
  assign(Iesire,'bfs.out');
  rewrite(Iesire);
  for i:=1 to n do write(Iesire,q[i],' ');
  close(Iesire);
end;

begin
  Citeste;
  Calculeaza;
  Scrie;
end.