F. Рада и Ромашковая долина
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вчера Рада нашла портал, который может перемещать её в Ромашковую долину и обратно. Счастью Рады не было предела, но длилось оно недолго — она вдруг поняла, что не знает, где и когда будет кто-либо из Смешариков.

Ромашковая долина состоит из $$$n$$$ домиков и $$$m$$$ тропинок, соединяющих домики. Тропинки пронумерованы от $$$1$$$ до $$$m$$$. По тропинкам можно идти в обе стороны. Известно, что из любого домика можно дойти по тропинкам до любого другого домика, а также нет тропинки, соединяющей домик сам с собой. Ко всему прочему, любые два домика соединены не более чем одной тропинкой.

Рада знает, что Смешарики каждый день ходят из домика с номером $$$1$$$ в домик с номером $$$n$$$, но она не знает, по каким конкретно тропинкам они пойдут. Рада побывает в Ромашковой долине в каждый из следующих $$$q$$$ дней. В $$$k$$$-й день она будет находиться около домика с номером $$$c_k$$$.

Так как Рада не знает, по каким конкретно тропинкам будут идти Смешарики, её интересуют только те тропинки, по которым гарантированно пройдут Смешарики. Чтобы точно не пропустить кого-то из них, она хочет узнать номер ближайшей такой тропинки в каждый из дней. Рада слишком занята прогулками по Ромашковой долине, и поэтому она просит вас помочь ей определить номера требуемых тропинок.

Расстоянием от домика $$$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$$$) — количество дней, в которые Рада будет гулять по Ромашковой долине.

Следующие $$$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
Примечание

Во всех дальнейших объяснениях обозначим переход из домика $$$a$$$ в домик $$$b$$$ по тропинке с номером $$$c$$$, как $$$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)$$$.