#include<cstdlib>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=200100;
int read()
{
	int x,f=1;
	char ch;
	while(ch=getchar(),!isdigit(ch))
	{
		if(ch=='-')f=-1;
	}
	x=ch-48;
	while(ch=getchar(),isdigit(ch))
	{
		x=x*10+ch-48;
	}
	return x*f;
}
void write(int x)
{
	 if(x<0)putchar('-'),x=-x;
     int cnt=0;char ch[30];
     while(ch[++cnt]=x%10+48,x/=10);
     while(putchar(ch[cnt]),--cnt);
     putchar('\n');
}
struct edge
{
	int f,t,n;
}a[maxn];
struct zheng
{
	int num,n;
}e[maxn];
int cnt,last[maxn];
int len,head[maxn];
void insert(int x,int y)
{
	a[++len].f=x;a[len].t=y;a[len].n=head[x];head[x]=len;
}
int n,m,D,ans[maxn],rt[maxn],fa[maxn][30],d[maxn];
#define k a[i].t
void dfs(int x)
{
	for(int i=head[x];i;i=a[i].n)
	{
		if(fa[x][0]==k)continue;
		d[k]=d[x]+1;
		fa[k][0]=x;
		dfs(k);
	}
}
#undef k
int lca(int x,int y)
{
	if(d[x]<d[y])swap(x,y);
	for(int j=D;j>=0;j--)
	{
		if(d[fa[x][j]]>=d[y])
		{
			x=fa[x][j];
		}
	}
	if(x==y)return x;
	for(int j=D;j>=0;j--)//注意要找到等于0 
	{
		if(fa[x][j]!=fa[y][j])
		{
			x=fa[x][j];y=fa[y][j];
		}
	}
	return fa[x][0];
}
int main()
{
	freopen("cowpol.in","r",stdin);
	freopen("cowpol.out","w",stdout);
	n=read(),m=read();
	int root=0;
	for(int i=1;i<=n;i++)
	{
		int x=read(),y=read();
		if(!y)root=i;
		else insert(y,i);
		e[++cnt].num=i;
		e[cnt].n=last[x];
		last[x]=cnt;
	}
	d[root]=1;
	dfs(root);
	D=log(n*1.0)/log(2.0);
	for(int j=1;j<=D;j++)
	{
		for(int i=1;i<=n;i++)
		{
			fa[i][j]=fa[fa[i][j-1]][j-1];
		}
	}
	for(int j=1;j<=m;j++)
	{
		int x=e[last[j]].num;
		int maxx=0,a=0;
		for(int i=last[j];i;i=e[i].n)
		{
			int k=e[i].num;
			if(k==x)continue;
			int l=lca(x,k);
			if(maxx<d[x]+d[k]-2*d[l])maxx=d[x]+d[k]-2*d[l],a=k;
		}
		int ans=0;x=a;
		for(int i=last[j];i;i=e[i].n)
		{
			int k=e[i].num;
			if(k==x)continue;
			int l=lca(x,k);
			if(ans<d[x]+d[k]-2*d[l])ans=d[x]+d[k]-2*d[l];
		}
		write(ans);
	}
    //system("pause");
}