#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
const int MAX=200000+10;
vector<int>C[MAX/2];
vector<int>A[MAX];
struct Edge{
	int t,next;
	Edge(){
		next=0;
	}
}E[MAX*2];
int ans[MAX/2]={0};
int fa[MAX];
int d[MAX];
int vis[MAX]={0};
int head[MAX]={0};
int pol[MAX];
int tot=1;
int pla[MAX/2]={0};
int vis1[MAX]={0};
inline void addedge(int x,int y){
	E[tot].t=y,E[tot].next=head[x],head[x]=tot++;
	E[tot].t=x,E[tot].next=head[y],head[y]=tot++;
}
inline int find(int x){
	if(x==fa[x])
		return x;
	return fa[x]=find(fa[x]);
}
inline void tarjan_LCA(int x){
	vis[x]=1;
	for(int i=0;i<A[x].size();i++){
		int u=A[x][i];
		if(!vis[u]){
			tarjan_LCA(u);
			fa[u]=x;
		}
	}
	for(int i=head[x];i;i=E[i].next){
		int u=E[i].t;
		if(vis[u]){
			int lca=find(u);
			ans[pol[x]]=max(ans[pol[x]],d[u]+d[x]-2*d[lca]);
		}
	}
}
inline void read(int& x){
	x=0;
	char c=getchar();
	while(c<'0'||c>'9')
		c=getchar();
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+c-'0';
		c=getchar();
	}
}
int main(){
	freopen("cowpol.in","r",stdin);
	freopen("cowpol.out","w",stdout);
	int n,k;
	read(n);
	read(k);
	int y;
	int kc;
	for(int i=1;i<=n;i++){
		read(pol[i]);
		read(y);
		if(y!=0){
			A[i].push_back(y);
			A[y].push_back(i);
		}
		if(y==0)
			kc=i;
		C[pol[i]].push_back(i);
	}
	queue<int>q;
	q.push(kc);
	d[kc]=1;
	vis1[kc]=1;
	while(!q.empty()){
		int cd=q.front();
		q.pop();
		for(int i=0;i<A[cd].size();i++){
			int u=A[cd][i];
			if(!vis1[u]){
				d[u]=d[cd]+1;
				vis1[u]=1;
				q.push(u);
			}
		}
	}
	d[0]=0;
	for(int i=1;i<=n;i++)
		if(d[i]>d[pla[pol[i]]])
			pla[pol[i]]=i;
	for(int i=1;i<=n;i++)
		if(i!=pla[pol[i]]){
			addedge(i,pla[pol[i]]);
		}
	for(int i=1;i<=n;i++)
		fa[i]=i;
	tarjan_LCA(kc);
	for(int i=1;i<=k;i++)
		printf("%d\n",ans[i]);
	/*for(int i=1;i<=n;i++){
		for(int j=head[i];j;j=E[j].next)
			printf("%d ",E[j].t);
		printf("\n");
	}*/
return 0;
}