← 返回题目列表

Codeforces · 2132/F

F. 拉达和洋甘菊谷

中文机器翻译题面 查看原题

昨天,拉达发现了一个传送门,可以将她传送到洋甘菊谷并返回。拉达的幸福是无限的,但它并没有持续多久——她突然意识到她不知道斯梅沙里基人会在何时何地。

洋甘菊谷由 $$$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$$$。

示例

输入
复制

3
3 3
1 2
2 3
3 1
1
1
5 4
1 2
2 3
3 4
4 5
3
1
2
3
7 6
1 2
1 5
2 3
3 4
5 7
6 7
7
1
2
3
4
5
6
7

输出
复制

-1 
1 1 2 
2 2 2 2 2 5 5 

输入
复制

2
5 4
4 2
4 1
5 1
3 5
5
1
2
3
4
5
6 6
1 2
2 3
3 4
4 5
5 2
5 6
2
3
4

输出
复制

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)$$$。