var t:array[1..100000] of longint;
    x,y:array[1..1000000] of longint;
    b1,b2:array[1..1shl 17] of char;
    b:boolean;
    n,m,i,s:longint;
BEGIN
  assign(input,'bfs.in');
  settextbuf(input,b1);
  reset(input);
  readln(n,m,s);
  for i:=1 to m do
  readln(x[i],y[i]);
  close(input);
  for i:=1 to n do
  t[i]:=-1;
  t[s]:=0;
  b:=true;
  while b do
    begin
      b:=false;
      for i:=1 to m do
        if (t[x[i]]<>-1) and ((t[y[i]]>t[x[i]]+1) or (t[y[i]]=-1) ) then
        begin
        t[y[i]]:=t[x[i]]+1;
        b:=true
        end;
    end;

  assign(output,'bfs.out');
  settextbuf(output,b2);
  rewrite(output);
  for i:=1 to n do
  write(t[i],' ');
  close(output);
end.