CF2132F Rada and the Chamomile Valley

昨天，Rada 发现了一个可以将她传送到 Chamomile 山谷并返回的传送门。Rada 的幸福无以言表，但好景不长——她突然意识到，她并不知道 Smeshariki 们会在什么时间、什么地点出现。 Chamomile 山谷由 $n$ 个房屋和 $m$ 条小路组成，这些小路连接着房屋。小路编号从 $1$ 到 $m$。你可以沿着小路双向行走。已知从任意一个房屋出发，都可以通过这些小路到达任意其他房屋，没有小路连接一个和它自身相同的房屋，即没有自环。此外，任意两座房屋之间至多只有一条小路相连。 Rada 知道 Smeshariki 每天都会从 $1$ 号房屋走到 $n$ 号房屋，但她并不知道他们具体会选择哪些小路。Rada 会在接下来的 $q$ 天里，每天都在 Chamomile 山谷中。在第 $k$ 天，她会在 $c_k$ 号房屋。 由于 Rada 不知道 Smeshariki 具体会走哪些小路，她只关心那些他们一定会经过的小路。为了确保不会错过任何一条，她希望知道每天距离她最近的这样的小路的编号。Rada 太忙于在 Chamomile 山谷中散步了，所以她请你帮忙确定所需的小路编号。 从房屋 $c$ 到连接房屋 $a$ 和 $b$ 的小路的距离定义为 $\min(\rho(a, c), \rho(b, c))$，其中 $\rho(a, b)$ 表示从房屋 $a$ 出发到达房屋 $b$ 至少需要经过的小路数。

输入的第一行包含一个整数 $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$ 号房屋的小路。小路按编号顺序给出，即第 $1$ 条小路描述在前，第 $2$ 条小路描述在后，依此类推直到第 $m$ 条。 接下来一行包含一个整数 $q$（$1 \leq q \leq 2 \cdot 10^5$）——表示 Rada 在 Chamomile 山谷中散步的天数。 接下来的 $q$ 行，每行包含一个整数 $c$（$1 \leq c \leq n$）——表示 Rada 在当天所在的房屋编号。 保证从任意房屋出发都可以通过小路到达任意其他房屋，且没有自环，任意两房屋之间至多只有一条小路。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$，$m$ 的总和不超过 $2 \cdot 10^5$，$q$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出每一天的答案。如果某一天有多条符合条件的小路，输出编号最小的那一条。如果没有符合条件的小路，输出 $-1$。

在所有后续解释中，我们用 $a \xrightarrow{c} b$ 表示通过编号为 $c$ 的小路从房屋 $a$ 到房屋 $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)$。 由 ChatGPT 4.1 翻译