const f ='bfs.in'; g = 'bfs.out';
var
    nvec,cost,q : array[0..10001] of longint;
    a : array[0..10001,0..10001] of longint;
    ii, jj, n, m : longint;
    st, x, y : longint;

procedure bfs( nod : longint );
    var
        l, i, j : longint;
    begin
        for i := 1 to n do cost[i] := -1;
        //fillchar(cost, sizeof(cost),1);
        l := 1;
        cost[nod] := 0;
        q[l] := nod;
        for i := 1 to l do
            for j := 1 to nvec[q[l]] do
                if cost[a[q[i],j]] = -1 then begin
                    inc( l );
                    q[l] := a[q[i],j];
                    cost[q[l]] := cost[q[i]] + 1;
                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,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.