Program latime;
const INF = 99999999;
type lista=^cell;
     cell = record
                    nod : longint;
                    cost : longint;
                    pred : lista;
     end;
var lda : array[1..10000] of lista;
    viz,coada,d : array[1..10000] of longint;
    i,n,j,a,b,c,m,s : longint;
    r: lista;

procedure add( nod,cost : longint; var p : lista);
var r : lista;
   begin
        new(r);
        r^.nod:=nod;
        r^.cost:=cost;
        r^.pred:=p;
        p:=r;
   end;

procedure bfs ( nod : longint );
 var beg,sf : longint;
   begin
        viz[nod]:=1;   coada[1]:=nod;  beg:=1;   sf:=1;

        while beg<=sf do
                        Begin
                          r:=lda[coada[beg]];
                          while r<>nil do Begin
                                       if viz[r^.nod]=0 then Begin
                                                               viz[r^.nod]:=1;
                                                               sf:=sf+1;
                                                               coada[sf]:=r^.nod;
                                       if D[coada[beg]]+1<D[r^.nod] then
                                          D[r^.nod]:=D[coada[beg]]+1;
                                                                end;
                                       r:=r^.pred; end;
                                       beg:=beg+1;
                             end;

end;

begin
    assign(input,'bfs.in'); reset(input);
    assign(output,'bfs.out'); rewrite(output);
    readln(n,m,s);
    for i:=1 to m do begin
                          readln(a,b);
                          add(b,1,lda[a]);
                          end;

    for i:=1 to n do d[i]:=INF; d[s]:=0;
    bfs(2);
    for i:=1 to n do
       if D[i]=INF then write(-1,' ')
                    else write(D[i],' ');

    close(input);
    close(output);
end.