给定一棵树,其中 $$$n$$$ 个顶点以顶点 $$$1$$$ 为根。当樱子带着她的猫谢菲尔走过它时,她分心了,谢菲尔逃跑了。
为了帮助樱子,小介记录了他的 $$$q$$$ 猜测。在第 $$$i$$$ 次猜测中,他假设 Chefir 在顶点 $$$v_i$$$ 处迷路并且拥有 $$$k_i$$$ 耐力。
此外,对于每个猜测,Kosuke 都假设 Chefir 可以沿着边缘移动任意次数:
- 从顶点$$$a$$$到顶点$$$b$$$,如果$$$a$$$是$$$b$$$的祖先$$$^{\text{∗}}$$$,则耐力不会改变;
- 从顶点$$$a$$$到顶点$$$b$$$,如果$$$a$$$不是$$$b$$$的祖先,那么Chefir的耐力会减少$$$1$$$。
如果Chefir的耐力为$$$0$$$,他就无法进行第二种类型的动作。
对于每个假设,您的任务是找到 Chefir 从顶点 $$$v_i$$$ 到具有 $$$k_i$$$ 耐力的最远顶点的距离。
输入
第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。
每个测试用例描述如下:
- 第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 树中的顶点数。
- 接下来的 $$$n-1$$$ 行包含树的边缘。保证给定的边形成一棵树。
- 下一行由一个整数 $$$q$$$ $$$(1\le q\le 2 \cdot 10^5)$$$ 组成,表示 Kosuke 猜测的次数。
- 接下来的 $$$q$$$ 行描述了 Kosuke 的猜测,其中有两个整数 $$$v_i$$$, $$$k_i$$$ $$$(1\le v_i \le n, 0 \le k_i\le n)$$$。
保证所有测试用例的 $$$n$$$ 之和与 $$$q$$$ 之和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例和每个猜测,输出 Chefir 从具有 $$$k_i$$$ 耐力的起点 $$$v_i$$$ 可以到达的最远顶点的最大距离。
示例
输入 #1
3 5 1 2 2 3 3 4 3 5 3 5 1 3 1 2 0 9 8 1 1 7 1 4 7 3 4 9 3 2 1 5 3 6 7 6 0 2 3 6 2 8 2 2 4 9 2 6 3 6 2 1 2 5 2 4 5 6 4 3 3 3 1 1 3 6 5
输出 #1
2 1 2 0 5 2 4 5 5 5 1 3 4
注意
在第一个示例中:
- 在第一个查询中,你可以从顶点$$$5$$$到顶点$$$3$$$(之后你的体力会减少$$$1$$$,变成$$$0$$$),然后你可以到顶点$$$4$$$;
- 在第二个查询中,从具有 $$$1$$$ 耐力的顶点 $$$3$$$ 开始,您只能到达顶点 $$$2$$$、$$$3$$$、$$$4$$$ 和 $$$5$$$;
- 在第三个查询中,从具有 $$$0$$$ 耐力的顶点 $$$2$$$ 开始,您只能到达顶点 $$$2$$$、$$$3$$$、$$$4$$$ 和 $$$5$$$;