type mat=record
        d:array[0..1000] of integer;
end;
const f ='bfs.in'; g = 'bfs.out';
var
    nvec,cost,q : array[0..100001] of longint;
    a : array[0..100000] of mat;
    //a : array[0..100001,0..10001] of longint;
    ii, jj, n, m : longint;
    st, x, y : longint;

procedure bfs( nod : longint );
    var
        ss, l, i, j : longint;
    begin
        for i := 1 to n do cost[i] := -1;
        //fillchar(cost, sizeof(cost),1);
        ss := 0;
        l := 1;
        cost[nod] := 0;
        q[ss] := nod;
        //for i := 1 to l do
        while ss<=l do begin
            for j := 1 to nvec[q[ss]] do
                if cost[a[q[ss]].d[j]] = -1 then begin
                    inc( l );
                    q[l] := a[q[ss]].d[j];
                    cost[q[l]] := cost[q[ss]] + 1;
                end;
            inc( ss );
            end;

    end;

begin
    assign( input,f ); reset( input );
    assign( output,g ); rewrite( output );
    readln( n, m, st );
    for ii := 1 to m do begin
        readln( x,y );
        nvec[x] := nvec[x] + 1;
        //nvec[y] := nvec[y] + 1;
        a[x].d[nvec[x]] := y;
        //a[y,nvec[y]] := x;
    end;
    {
    for ii := 1 to n do begin
        for jj := 1 to nvec[ii] do write(a[ii,jj],' ');
        writeln;
    end;
    writeln;
    }
    bfs(st);
    for ii := 1 to n do write(cost[ii],' ');
end.