由于 Hayate 没有从圣诞老人那里得到任何圣诞礼物,所以他只能解决树查询问题。
Hayate 有一个包含 $$$n$$$ 节点的树。
Hayate 现在希望您回答 $$$q$$$ 查询。每个查询由一个节点 $$$x$$$ 和 $$$k$$$ 其他附加节点 $$$a_1,a_2,\ldots,a_k$$$ 组成。这些 $$$k+1$$$ 节点保证都是不同的。
对于每个查询,您必须在删除节点 $$$a_1,a_2,\ldots,a_k$$$ 以及连接到至少一个节点 $$$a_1,a_2,\ldots,a_k$$$ 的所有边后找到从节点 $$$x^\dagger$$$ 开始的最长简单路径的长度。
$$$^\dagger$$$ 从节点 $$$x$$$ 开始的长度为 $$$k$$$ 的简单路径是一系列不同的节点 $$$x=u_0,u_1,\ldots,u_k$$$,使得节点 $$$u_{i-1}$$$ 和 $$$u_i$$$ 之间存在一条边,对于所有 $$$1 \leq i \leq k$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) - 树的节点数和查询数。
以下 $$$n - 1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) - 表示节点 $$$u$$$ 和 $$$v$$$ 之间的边。保证给定的边形成一棵树。
以下 $$$q$$$ 行描述了查询。每行包含整数 $$$x$$$、$$$k$$$ 和 $$$a_1,a_2,\ldots,a_k$$$ ($$$1 \leq x \leq n$$$, $$$0 \leq k < n$$$, $$$1 \leq a_i \leq n$$$) — 起始节点、已删除节点的数量和已删除节点。
保证对于每个查询,$$$x,a_1,a_2,\ldots,a_k$$$ 都是不同的。
保证所有查询的 $$$k$$$ 总和不会超过 $$$2 \cdot 10^5$$$。
输出
对于每个查询,输出一个整数表示该查询的答案。
示例
输入 #1
7 7 1 2 1 3 3 4 2 5 2 6 6 7 2 0 2 1 1 2 2 1 6 3 1 4 3 1 1 5 0 5 2 1 6
输出 #1
3 2 1 4 1 4 1
输入 #2
4 4 1 2 1 3 2 4 2 1 3 3 1 4 2 1 4 2 3 1 3 4
输出 #2
1 2 2 0
注意
第一个例子中,树如下:
在第一个查询中,没有丢失任何节点。从节点 $$$2$$$ 开始的最长简单路径是 $$$2 \to 1 \to 3 \to 4$$$。因此,答案是$$$3$$$。
在第三个查询中,节点 $$$1$$$ 和 $$$6$$$ 丢失,树如下所示。从节点 $$$2$$$ 开始的最长简单路径是 $$$2 \to 5$$$。因此,答案是$$$1$$$。