program bfs2;
const Nmax = 100005;
      Mmax = 1000005;
var f, g:text;
    n, m, s, i, j, k:longint;
    start, coada, viz:array[1..Nmax] of longint;
    t:array[0..1,1..Mmax] of longint;
    bufin, bufout:array[1..1 shl 17] of char;
procedure bfs(nod:longint);
var p, u, z:longint;
begin
   p := 1; u := 1;
   coada[p] := nod;
   viz[nod] := 1;
   while p <= u do
      begin
         z := start[coada[p]];
         while z <> 0 do
            begin
               if viz[t[0, z]] = 0 then
                  begin
                     inc(u);
                     coada[u] := t[0, z];
                     viz[t[0, z]] := viz[coada[p]] + 1;
                  end;
               z := t[1, z];
            end;
         inc(p);
      end;
end;
begin
   assign(f, 'bfs.in'); reset(f);
   assign(g, 'bfs.out'); rewrite(g);
   readln(f, n, m, s);
   for k := 1 to m do
      begin
         readln(f, i, j);
         t[0, k] := j;
         t[1, k] := start[i];
         start[i] := k;
      end;
   bfs(2);
   for i := 1 to n do
      write(g, viz[i] - 1,' ');

   close(f); close(g);
end.