动态树的直径

题目描述

给定一棵树，动态加入叶子，输出每次加入叶子以后树的直径长度，$n \leq 10^5， 1 \le q \le 1000$。

输入

第一行空格隔开的两个数 n 和 q；表示下面的树有n个结点，q 表示要动态加入叶子结点个数。 第二行开始的 n-1 行，表示树的边。 第 n+1 行开始共 q 行，每行两个数 u ， v，表示叶子结点 v 连接在 u 结点上。

输出

q 行，每行表示新添加叶子结点后，树的直径长度。

样例

3 1
1 2
1 3
2 4

3

样例解释

未加入叶子结点前树的形态。

加入叶子结点后的树

数据规模

$10\%, n \le 100, q = 1$，

$其中30\%的数据中，q = 1$，

$其中10\%的数据中，n \le 1000, q = 2$，

$100\%的数据, 2 \le n \le 10^5,0\le q \le 10^3$。

Limitation

1s, 1024KiB for each test case.