var
  n,k,time,i,m,j,max,lg,t,num,total,tota:longint;
  fa,dis:array[-1..1000000]of longint;
  v:Array[0..300000]of boolean;
  point,now,poin,next,nex,first,firs:array[-1..500000]of longint;
  p:array[-1..300000,-1..20]of longint;

procedure addpage(x,y:longint);
begin
  inc(total);
  point[total]:=y;
  next[total]:=first[x];
  first[x]:=total;
end;

procedure addpag(x,y:longint);
begin
  inc(tota);
  poin[tota]:=y;
  nex[tota]:=firs[x];
  firs[x]:=tota;
end;

procedure go(k,s:longint);
var
  i:longint;
begin
  v[k]:=true;
  dis[k]:=s;
  i:=first[k];
  while i>0 do
  begin
    j:=point[i];
    if not v[j] then
    begin
      fa[j]:=k;
      go(j,s+1);
    end;
    i:=next[i];
  end;
end;

function cal(xx,yy:longint):longint;
var
  x,y,z,nn,cha,k,i,lca:longint;
begin
  x:=xx;
  y:=yy;
  if dis[x]>dis[y] then
  begin
    z:=x;
    x:=y;
    y:=z;
  end;
  nn:=y;
  if x=1 then exit(dis[y]);
  cha:=trunc(ln(dis[y])/ln(2));
  for i:=cha downto 0 do
  if (dis[p[y,i]]>=dis[x])and(p[y,i]<>-1) then y:=p[y,i];

  if x=y then exit(dis[nn]-dis[x]);

  k:=trunc(ln(dis[x])/ln(2));

  for i:=k downto 0 do
  if (p[x,i]<>p[y,i])and(p[x,i]<>-1) then
  begin
    x:=p[x,i];
    y:=p[y,i];
  end;
  lca:=fa[x];
  cal:=dis[xx]+dis[yy]-2*dis[lca];
end;

begin
  assign(input,'cowpol.in'); reset(input);
  assign(output,'cowpol.out'); rewrite(output);
  readln(n,m);
  for i:=1 to n do
  begin
    readln(k,j);
    if j<>0 then
    begin
      addpage(i,j);
      addpage(j,i);
    end;

    addpag(k,i);
  end;

  go(1,0);

  lg:=trunc(ln(n)/ln(2));
  for i:=1 to n do p[i,0]:=fa[i];

  for j:=1 to lg do
   for i:=1 to n do
   p[i,j]:=-1;

  for j:=1 to lg do
   for i:=1 to n do
   p[i,j]:=p[p[i,j-1],j-1];

  for time:=1 to m do
  begin
    max:=-maxlongint;
    t:=0;
    i:=firs[time];
    while i>0 do
    begin
      j:=poin[i];
      inc(t);
      now[t]:=j;
      i:=nex[i];
    end;
    for i:=1 to t do
     for j:=i+1 to t do
     begin
       num:=cal(now[i],now[j]);
       if num>max then max:=num;
     end;
    writeln(max);
  end;
  close(input);
  close(output);
end.