记录编号	308497	评测结果	AAAAAAAAAAAAA
题目名称	[USACO Hol10] 政党	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	4.400 s
提交时间	2016-09-18 08:02:11	内存使用	18.24 MiB

//KZNS
#include <cstdio>
#include <vector>
using namespace std;
#define Nmax 200003
#define Mmax 100003
int N, M;
vector<int> tr[Nmax], zd[Mmax];
inline int input() {
	int ans = 0;
	char c = getchar();
	while (!('0' <= c && c <= '9'))
		c = getchar();
	while ('0' <= c && c <= '9') {
		ans = ans * 10 + c - '0';
		c = getchar();
	}
	return ans;
}
void rin() {
	N = input();
	M = input();
	int a, b;
	for (int i = 1; i <= N; i++) {
		a = input();
		b = input();
		zd[a].push_back(i);
		tr[b].push_back(i);
	}
}
int fas[Nmax][20] = {0};
int ddp[Nmax] = {0};
void DFS(int x, int dp) {
	ddp[x] = dp;
	int t;
	for (int i = 0; i < tr[x].size(); i++) {
		t = tr[x][i];
		fas[t][0] = x;
		DFS(t, dp+1);
	}
}
void lcafir() {
	for (int j = 1; j < 20; j++)
		for (int i = 1; i <= N; i++)
			fas[i][j] = fas[fas[i][j-1]][j-1];
}
inline int lca(int a, int b) {
	if (ddp[a] > ddp[b]) {
		for (int j = 19; j >= 0; j--)
			if (ddp[fas[a][j]] >= ddp[b])
				a = fas[a][j];
	}
	else {
		for (int j = 19; j >= 0; j--)
			if (ddp[fas[b][j]] >= ddp[a])
				b = fas[b][j];
	}
	if (a == b)
		return a;
	for (int j = 19; j >= 0; j--)
		if (fas[a][j] != fas[b][j])
			a = fas[a][j], b = fas[b][j];
	return fas[a][0];
}
void fir() {
	DFS(0, 0);
	lcafir();
}
void work() {
	int a, b, t;
	int ans;
	int dis;
	for (int i = 1; i <= M; i++) {
		a = zd[i][0];
		ans = 0;
		for (int j = 1; j < zd[i].size(); j++) {
			t = zd[i][j];
			dis = ddp[a] + ddp[t] - 2 * ddp[lca(a, t)];
			if (dis > ans) {
				ans = dis;
				b = t;
			}
		}
		for (int j = 1; j < zd[i].size(); j++) {
			t = zd[i][j];
			ans = max(ans, ddp[b] + ddp[t] - 2 * ddp[lca(b, t)]);
		}
		printf("%d\n", ans);
	}
}
int main() {
	freopen("cowpol.in", "r", stdin);
	freopen("cowpol.out", "w", stdout);
	rin();
	fir();
	work();
	return 0;
}
//UBWH