#include<stdio.h>
#include<ctype.h>
#include<string.h>
#include<algorithm>
namespace _tool{
#define INF 0x7f7f7f7f
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((l+r)>>1)
#define _upsize f[rt]=f[rt<<1]+f[rt<<1|1];
#define maxn 500010
#define fre freopen("cowpol.in","r",stdin);freopen("cowpol.out","w",stdout);
#define _max(a,b) ((a)>(b)?(a):(b))
#define _min(a,b) ((a)<(b)?(a):(b))
int _log2(const int &x){int k=0;while(1<<(k+1)<=x)k++;return k;}
int _read(){int ret,neg;char ch;ret=neg=0;while(!isdigit(ch=getchar())&&ch!='-');if(ch=='-')neg=1,ch=getchar();while(ret=ret*10+ch-'0',isdigit(ch=getchar()));if(neg)ret=-ret;return ret;}
}
using namespace _tool;
using namespace std;
struct _tree{
	int to,next;
}e[maxn<<1],gcd[maxn<<1];
int n,m,len=0,cnt=0,ans;
int head[maxn],fa[maxn],Dp[maxn],size[maxn],son[maxn],top[maxn],prev[maxn];
void _set(int prt,int son){
	e[++len].to=son,e[len].next=head[prt],head[prt]=len;
}
void _set1(int prt,int son){
	gcd[++cnt].to=son,gcd[cnt].next=prev[prt],prev[prt]=cnt;
}
#define to e[i].to
void _dfs(int rt){
	size[rt]=1;
	for(int i=head[rt];i;i=e[i].next)
	if(!size[to]){
		fa[to]=rt,Dp[to]=Dp[rt]+1;
		_dfs(to);
		size[rt]+=size[to];
		if(size[son[rt]]<size[to])son[rt]=to;
	}
}
void _dfs(int rt,int tp){
	top[rt]=tp;
	if(son[rt])_dfs(son[rt],tp);
	for(int i=head[rt];i;i=e[i].next)
	if(!top[to])_dfs(to,to);
}
#undef to
int _query(int x,int y){
	int t; 
	while(top[x]^top[y]){
		if(Dp[top[x]]<Dp[top[y]])t=x,x=y,y=t;
		x=fa[top[x]];
	}
	if(Dp[x]>Dp[y])t=x,x=y,y=t;
	return x;
}
bool _Rabit(),_RABIT=_Rabit();int main(){;}
bool _Rabit(){
	fre
	n=_read(),m=_read();
	for(int a,p,i=1;i<=n;i++){
		a=_read(),p=_read();
		_set1(a,i);
		_set(p,i),_set(i,p);
	}
	Dp[1]=1,fa[1]=1;_dfs(1);_dfs(1,1);
	for(int a,sonn,v=1;v<=m;v++){
		ans=-INF;sonn=a=gcd[prev[v]].to;
		for(int k,b,i=gcd[prev[v]].next;i;i=gcd[i].next){
			b=gcd[i].to;k=_query(a,b);
			if(ans<Dp[a]+Dp[b]-Dp[k]-Dp[k])
				ans=Dp[a]+Dp[b]-Dp[k]-Dp[k],sonn=b;
		}
		for(int i=prev[v];i;i=gcd[i].next)
			if(gcd[i].to^sonn)
				ans=_max(ans,Dp[sonn]+Dp[gcd[i].to]-(Dp[_query(sonn,gcd[i].to)]<<1));
		printf("%d\n",ans);
	}
}