program graf;
type
liste=^date;
date=record
m:longint;
next:liste;
end;
type
tabel=array[0..100001] of liste;
tab=array[0..100001] of longint;
var
fr,coada,d:tab;
a:liste;
t:tabel;
n,m,k,i,ul,pr,x,y:longint;
f1,f2:text;
begin
assign (f1,'bfs.in');
assign (f2,'bfs.out');
reset (f1);
rewrite (f2);
readln (f1,n,m,k);
for i:=1 to m do begin
readln (f1,x,y);
new(a);
a^.m:=y;
a^.next:=t[x];
t[x]:=a;
end;
for i:=1 to n do
d[i]:=9999999; d[k]:=0;
fr[k]:=1; pr:=1; ul:=1; coada[pr]:=k;
while pr<=ul do begin
a:=t[coada[pr]];
while a<>nil do begin
if fr[a^.m]=0 then begin
fr[a^.m]:=1;
ul:=ul+1;
coada[ul]:=a^.m;
if d[coada[pr]]+1<d[a^.m] then d[a^.m]:=d[coada[pr]]+1;
end;
a:=a^.next;
end;
pr:=pr+1;
end;
for i:=1 to n do
if d[i]=9999999 then write (f2,-1,' ') else
write (f2,d[i],' ');
close (f1);
close (f2);
end.