program bfs;
type pcelula=^celula;
     celula=record
        x:longint;
        adr:pcelula;
        end;

var graf:array[1..100000] of pcelula;
    q,dist:array[1..100000] of longint;
    viz:array[1..100000] of boolean;
    bufin,bufout:array[1..100000] of byte;
    f,g:text;
    n,m,s,i,x,y,iq,sq,nod:longint;
    p:pcelula;

begin
assign(f,'bfs.in'); reset(f);
assign(g,'bfs.out'); rewrite(g);
settextbuf(f,bufin);
settextbuf(g,bufout);
readln(f,n,m,s);
for i:=1 to n do begin
         graf[i]:=nil;
         dist[i]:=-1;
         viz[i]:=false;
         end;
for i:=1 to m do
        begin
        readln(f,x,y);
        new(p);
        p^.x:=y;
        p^.adr:=graf[x];
        graf[x]:=p;
        end;
iq:=1; sq:=1;
viz[s]:=true;
q[iq]:=s;
dist[s]:=0;
while (iq<=sq) do begin
        nod:=q[iq];
        iq:=iq+1;
        p:=graf[nod];
        while p<>nil do
                begin
                if viz[p^.x]=false then
                        begin
                        sq:=sq+1;
                        q[sq]:=p^.x;
                        viz[p^.x]:=true;
                        dist[p^.x]:=dist[nod]+1;
                        end;
                p:=p^.adr;
                end;
        end;
for i:=1 to n do
        write(g,dist[i],' ');
close(f);
close(g);
end.