program parcurgerea_unui_graf_in_latime;
var v:array[1..2,1..100000] of longint;
    b1,b2:array[1.. 1 shl 15] of char;
    i,j,m,n,s:longint;
    b:boolean;
    d:array[1..100000] of longint;
begin
assign(input,'bfs.in'); settextbuf(input,b1); reset(input);
assign(output,'bfs.out'); settextbuf(output,b2); rewrite(output);
readln(n,m,s);
for i:=1 to m do readln(v[1,i],v[2,i]);
close(input);
d[s]:=1;
b:=true;
while b do begin
           b:=false;
           for i:=1 to m do if (d[v[1,i]]<>0)and((d[v[2,i]]=0) or (d[v[2,i]]>d[v[1,i]]+1))
                                then begin
                                     d[v[2,i]]:=d[v[1,i]]+1;
                                     b:=true;
                                     end;
           end;
for i:=1 to n do write(d[i]-1,' ');
close(output);
end.