昨天,拉达发现了一个传送门,可以将她传送到洋甘菊谷并返回。拉达的幸福是无限的,但它并没有持续多久——她突然意识到她不知道斯梅沙里基人会在何时何地。
洋甘菊谷由 $$$n$$$ 房屋和连接房屋的 $$$m$$$ 车道组成。车道编号从 $$$1$$$ 到 $$$m$$$。您可以沿着两个方向的小巷行走。众所周知,从任何房屋,您都可以通过巷道到达任何其他房屋,并且没有任何巷道将房屋与其本身连接起来。而且,任意两栋房子最多有一条巷子相连。
Rada 知道 Smeshariki 每天从门牌号 $$$1$$$ 步行到门牌号 $$$n$$$,但她不知道他们会走哪条具体车道。 Rada 将在接下来的 $$$q$$$ 天出现在洋甘菊谷。在第 $$$k$$$ 天,她将在 $$$c_k$$$ 号门牌处。
由于 Rada 不知道 Smeshariki 将采用哪些特定车道,因此她只对他们将采用的那些车道感兴趣 绝对 使用。为了确保她不会错过任何一条,她想知道每天最近的此类车道的索引。拉达正忙着在洋甘菊谷漫步,所以她请你帮助她确定所需的车道索引。
从房屋 $$$c$$$ 到连接房屋 $$$a$$$ 和 $$$b$$$ 的车道的距离定义为 $$$\rho(a, c)$$$ 和 $$$\rho(b, c)$$$ 中的最小值,其中 $$$\rho(a, b)$$$ 是从房屋号开始到达房屋号 $$$b$$$ 所需的最小车道数$$$a$$$。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。每个测试用例的描述如下。
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$n-1 \leq m \leq \min(\frac{n \cdot (n-1)}{2}, 2 \cdot 10^5)$$$) — 分别是房屋和车道的数量。
接下来的 $$$m$$$ 行包含两个整数 $$$u \neq v$$$ ($$$1 \leq u, v \leq n$$$) — 连接编号为 $$$u$$$ 和 $$$v$$$ 的房屋的车道。泳道按编号顺序给出,即首先描述第一泳道,然后是第二泳道、第三泳道,依此类推,直到第 $$$m$$$ 泳道。
接下来,给出一个整数 $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — Rada 将在洋甘菊谷行走的天数。
接下来的 $$$q$$$ 行每行包含一个整数 $$$c$$$ ($$$1 \leq c \leq n$$$) — 拉达当天所在的房子。
保证从任意一栋房屋,仅通过车道即可到达任意其他房屋,且房屋与自身之间不存在车道,且任意两栋房屋至多有一条车道相连。
保证所有测试用例的$$$n$$$总和不超过$$$2 \cdot 10^5$$$,所有测试用例的$$$m$$$总和不超过$$$2 \cdot 10^5$$$,所有测试用例的$$$q$$$总和不超过$$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出每一天的答案。如果任意一天有多个合适的车道,则输出带有 最小 索引属于合适的。如果没有需要的车道,则输出$$$-1$$$。
示例
输入复制
33 31 22 33 1115 41 22 33 44 531237 61 21 52 33 45 76 771234567
输出复制
-1 1 1 2 2 2 2 2 2 5 5
输入复制
25 44 24 15 13 55123456 61 22 33 44 55 25 6234
输出复制
3 3 3 3 3 1 6
注意
在所有进一步的解释中,我们将通过编号为 $$$c$$$ 的车道从房屋 $$$a$$$ 到房屋 $$$b$$$ 的过渡表示为 $$$a \xrightarrow{c} b$$$。
在第一个示例中,从房子 $$$1$$$ 到房子 $$$3$$$,您至少可以通过以下路径到达它:
$$1 \xrightarrow{3} 3$$
$$1 \xrightarrow{1} 2 \xrightarrow{2} 3$$
正如我们所看到的,这两条路径不共享任何公共车道,这意味着没有合适的车道。
在第二个示例中,可以注意到从 $$$1$$$ 到 $$$n$$$ 存在唯一路径:
$$1 \xrightarrow{1} 2 \xrightarrow{2} 3 \xrightarrow{3} 4 \xrightarrow{4} 5$$
可以看出,第 $$$v$$$ 个顶点的答案是 $$$\max(v-1,\ 1)$$$。