var     a:array[1..100000] of longint;
        v:array[1..2,1..1000000] of longint;
        n,m,s,i:longint;
        b:boolean;
        f,g:text;

begin
  assign(f,'bfs.in');
  assign(g,'bfs.out');
  reset(f);
  rewrite(g);
  readln(f,n,m,s);
  for i:=1 to m do
    readln(f,v[1,i],v[2,i]);
  for i:=1 to n do
    a[i]:=-1;
{  for i:=1 to m do
    if v[1,i]=s then
    if v[2,i]=s then a[s]:=0
    else a[v[2,i]]:=1;}
  a[s]:=0;
  b:=true;
  while b do
    begin
      b:=false;
      for i:=1 to m do
        if (a[v[1,i]]<>-1)and((a[v[2,i]]=-1)or(a[v[2,i]]>a[v[1,i]]+1)) then
          begin
            a[v[2,i]]:=a[v[1,i]]+1;
            b:=true;
          end;
    end;
  for i:=1 to n do
    write(g,a[i],' ');
  close(g);
end.