codeforces#P2132F. Rada and the Chamomile Valley
Rada and the Chamomile Valley
Description
Yesterday, Rada found a portal that can transport her to the Chamomile Valley and back. Rada's happiness knew no bounds, but it didn't last long — she suddenly realized that she didn't know where and when any of the Smeshariki would be.
The Chamomile Valley consists of $n$ houses and $m$ lanes connecting the houses. The lanes are numbered from $1$ to $m$. You can walk along the lanes in both directions. It is known that from any house, you can reach any other house via the lanes, and there is no lane connecting a house to itself. Moreover, any two houses are connected by at most one lane.
Rada knows that the Smeshariki walk every day from house number $1$ to house number $n$, but she doesn't know which specific lanes they will take. Rada will be in the Chamomile Valley on each of the next $q$ days. On the $k$-th day, she will be at house number $c_k$.
Since Rada does not know which specific lanes the Smeshariki will take, she is only interested in those lanes that they will definitely use. To ensure she does not miss any of them, she wants to know the index of the nearest such lane on each day. Rada is too busy strolling through the Chamomile Valley, so she asks you to help her determine the required lane indices.
The distance from house $c$ to the lane connecting houses $a$ and $b$ is defined as the minimum of $\rho(a, c)$ and $\rho(b, c)$, where $\rho(a, b)$ is the minimum number of lanes needed to reach house number $b$ starting from house number $a$.
The first line of the input contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of each test case follows.
The first line contains two integers $n$ and $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)$) — the number of houses and lanes, respectively.
The next $m$ lines contain two integers $u \neq v$ ($1 \leq u, v \leq n$) — a lane connecting houses numbered $u$ and $v$. The lanes are given in order of numbering, that is, the description of the first lane comes first, followed by the second, third, and so on up to the $m$-th lane.
Next, an integer $q$ ($1 \leq q \leq 2 \cdot 10^5$) is given — the number of days Rada will be walking in the Chamomile Valley.
The next $q$ lines each contain a single integer $c$ ($1 \leq c \leq n$) — the house at which Rada will be on that day.
It is guaranteed that from any house, you can reach any other house by only using the lanes, and there are no lanes from a house to itself, and any two houses are connected by at most one lane.
It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$, the sum of $m$ across all test cases does not exceed $2 \cdot 10^5$, and the sum of $q$ across all test cases does not exceed $2 \cdot 10^5$.
For each test case, output the answer for each of the days. If there are multiple suitable lanes on any of the days, output the lane with the smallest index among the suitable ones. If there are no required lanes, output $-1$.
Input
The first line of the input contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of each test case follows.
The first line contains two integers $n$ and $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)$) — the number of houses and lanes, respectively.
The next $m$ lines contain two integers $u \neq v$ ($1 \leq u, v \leq n$) — a lane connecting houses numbered $u$ and $v$. The lanes are given in order of numbering, that is, the description of the first lane comes first, followed by the second, third, and so on up to the $m$-th lane.
Next, an integer $q$ ($1 \leq q \leq 2 \cdot 10^5$) is given — the number of days Rada will be walking in the Chamomile Valley.
The next $q$ lines each contain a single integer $c$ ($1 \leq c \leq n$) — the house at which Rada will be on that day.
It is guaranteed that from any house, you can reach any other house by only using the lanes, and there are no lanes from a house to itself, and any two houses are connected by at most one lane.
It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$, the sum of $m$ across all test cases does not exceed $2 \cdot 10^5$, and the sum of $q$ across all test cases does not exceed $2 \cdot 10^5$.
Output
For each test case, output the answer for each of the days. If there are multiple suitable lanes on any of the days, output the lane with the smallest index among the suitable ones. If there are no required lanes, output $-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
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
-1
1 1 2
2 2 2 2 2 5 5
3 3 3 3 3
1 6
Note
In all further explanations, we denote the transition from house $a$ to house $b$ via the lane numbered $c$ as $a \xrightarrow{c} b$.
In the first sample, from house $1$ to house $3$, you can reach it via at least the following paths:
$$1 \xrightarrow{3} 3$$
$$1 \xrightarrow{1} 2 \xrightarrow{2} 3$$
As we can see, these two paths do not share any common lanes, which means there are no suitable lanes.
In the second sample, it can be noted that there is a unique path from $1$ to $n$:
$$1 \xrightarrow{1} 2 \xrightarrow{2} 3 \xrightarrow{3} 4 \xrightarrow{4} 5$$
As can be seen, the answer for the $v$-th vertex is $\max(v-1,\ 1)$.