Program parcurge_latime;
var fi,fo : text; t:boolean;
    i,m,n,s : longint;
    v:array[1..2,0..1000000] of longint;
    b:array[0..100000] of longint;

begin
    assign(fi,'bfs.in'); reset(fi); readln(fi,n,m,s);
    assign(fo,'bfs.out'); rewrite(fo); t:=true;  b[s]:=1;
    for i:=1 to m do readln(fi,v[1,i],v[2,i]);
    while t=true do begin
                    t:=false;
                    for i:=1 to m do
                       if (b[v[1,i]]<>0) and ((b[v[2,i]]=0) or (b[v[2,i]]>b[v[1,i]]+1))
                                       then begin
                                            t:=true;
                                            b[v[2,i]]:=b[v[1,i]]+1;
                                            end;
                    end;

    for i:=1 to n do write(fo,b[i]-1,' ');
    close(fi); close(fo);
end.