Program bfs;
 type list = ^cell;
      cell = record no:longint; ne:list; end;
 var f,g:text; a:array[1..100000,1..2]of list;
     b:array[1..100000]of boolean;
     c:array[1..100000]of longint;
     i,j,k,n,m,s:longint; l,ls,lf:list;
 begin
  assign (f,'bfs.in'); reset (f);
  assign (g,'bfs.out'); rewrite (g);
  readln (f,n,m,s);
  for i:=1 to n do a[i,1]:=nil;
  for i:=1 to m do begin
    readln (f,j,k);
    if a[j,1]=nil then begin
      new (a[j,1]);
      a[j,1]^.no:=k;
      a[j,1]^.ne:=nil;
      a[j,2]:=a[j,1];
    end else begin
      new (a[j,2]^.ne);
      a[j,2]:=a[j,2]^.ne;
      a[j,2]^.no:=k;
      a[j,2]^.ne:=nil;
    end;
  end;
  new (ls); ls^.no:=s; ls^.ne:=nil; lf:=ls;
  b[s]:=true; c[s]:=1;
  while ls<>nil do begin
    j:=ls^.no;
    a[j,2]:=a[j,1];
    while a[j,2]<>nil do begin
      if not b[a[j,2]^.no] then begin
        new (lf^.ne);
        lf:=lf^.ne;
        lf^.no:=a[j,2]^.no;
        lf^.ne:=nil;
        b[a[j,2]^.no]:=true;
        c[a[j,2]^.no]:=c[j]+1;
      end;
      a[j,2]:=a[j,2]^.ne;
    end;
    l:=ls^.ne;
    dispose (ls);
    ls:=l;
  end;
  for i:=1 to n do write (g,c[i]-1,' '); writeln (g);
  close (f); close (g);
 end.