Program parcurgere_latime;
var a:array [1..2,1..1000000] of longint;
    b:array [1..100000] of longint;
    b1,b2:array [1..1 shl 15] of char;
    i,n,m,s:longint;
    ok:boolean;
    fi,fo:text;
begin
 assign(fi,'bfs.in');
  assign(fo,'bfs.out');
 reset(fi);
  rewrite(fo);
 settextbuf(fi,b1);
 settextbuf(fo,b2);
 readln(fi,n,m,s);
 for i:=1 to m do readln(fi,a[1,i],a[2,i]);
  b[s]:=1; ok:=true;
 while ok do begin
        ok:=false;
         for i:=1 to m do
          if (b[a[1,i]]<>0) and (b[a[2,i]]=0) then begin
                                                  ok:=true;
                                                   b[a[2,i]]:=b[a[1,i]]+1;
                                                    end;
           end;
 for i:=1 to n do write(fo,b[i]-1,' ');
close(fo);
end.