type ref=^nod;
nod=record
    nr:longint;
    adr:ref;
    end;
var v:array[1..100000] of ref;
s:array[1..100000] of 0..1;
st:array[1..100000] of longint;
u,c,sf,cost,cost2,u2:ref;
n,m,varf,i,j,k,sum:longint;
f,g:text;
begin
assign(f,'bfs.in');
assign(g,'bfs.out');
reset(f);rewrite(g);
readln(f,n,m,varf);
for i:=1 to m do
    begin
    readln(f,j,k);
    if v[j]=nil then
       begin
       new(v[j]);
       v[j]^.nr:=k;
       v[j]^.adr:=nil;
       end
    else
        begin
        new(u);
        u^.adr:=v[j];
        u^.nr:=k;
        v[j]:=u;
        end;
    end;
for i:=1 to n do
    st[i]:=-1;
st[varf]:=0;
s[varf]:=1;
sum:=1;
new(c);
c^.adr:=nil;
c^.nr:=varf;
sf:=c;
new(cost);
cost^.adr:=nil;
cost^.nr:=0;
cost2:=cost;
repeat
      u:=v[c^.nr];
      while u<>nil do
            begin
            if s[u^.nr]=0 then
               begin
               new(u2);
               sum:=sum+1;
               u2^.adr:=nil;
               u2^.nr:=u^.nr;
               s[u^.nr]:=1;
               sf^.adr:=u2;
               sf:=u2;
               new(u2);
               u2^.adr:=nil;
               u2^.nr:=cost^.nr+1;
               st[u^.nr]:=u2^.nr;
               cost2^.adr:=u2;
               cost2:=u2;
               end;
            u:=u^.adr;
            end;
      if c<>nil then
         begin
         u:=c^.adr;
         u2:=cost^.adr;
         dispose(c);
         dispose(cost);
         c:=u;
         cost:=u2;
         end;
      if c=nil then
         break;
until sum=n;
for i:=1 to n do
    write(g,st[i],' ');
close(f);close(g);
end.