B. Путешествия во времени
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Вы обнаружили машину времени, которая перемещает вас между ключевыми моментами. К сожалению, вы не можете выбирать, в какой момент времени переместиться, но знаете порядок, состоящий из $$$k$$$ моментов времени $$$a_{i}$$$, в котором машина будет вас перемещать. Так как времени между перемещениями мало, то оказавшись в очередном ключевом моменте времени (в том числе после последнего перемещения во времени), вы можете проехать не более чем по одной существующей в данный момент времени дороге, выходящей из города, в котором вы оказались перед перемещением во времени.

Сейчас вы находитесь в городе $$$1$$$, и машина времени уже перенесла вас в момент времени $$$a_{1}$$$. Вы хотите как можно быстрее добраться до города $$$n$$$. Определите минимальное количество перемещений во времени, включая первое, которые нужно совершить, чтобы оказаться в городе $$$n$$$.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$t$$$ ($$$2 \le n \le 2 \cdot 10^5, 1 \le t \le 2 \cdot 10^5$$$) — количество городов в Берляндии и количество записей про ключевые моменты истории. Далее следует описание каждой из $$$t$$$ записей.

Первая строка описания каждой записи содержит одно целое число $$$m_{i}$$$ ($$$0 \le m_{i} \le \min \left(\frac{n(n-1)}{2}, 2 \cdot 10^5\right)$$$) — количество дорог в $$$i$$$-й записи.

Каждая из следующих $$$m_i$$$ строк содержит два целых числа $$$v_{j}$$$ и $$$u_{j}$$$ ($$$1 \le v_{j}, u_{j} \le n$$$, $$$v_{j} \neq u_{j}$$$) — номера городов, которые соединяет $$$j$$$-я дорога в $$$i$$$-й ключевой момент истории.

Следующая строка содержит одно целое число $$$k$$$ ($$$1 \le k \le 2 \cdot 10^5$$$) — количество моментов времени, между которыми будут происходить перемещения.

Следующая строка содержит $$$k$$$ целых чисел $$$a_1, a_2, \ldots, a_k$$$ ($$$1 \le a_{i} \le t$$$) — моменты времени, в которых вы будете оказываться после каждого перемещения.

Гарантируется, что сумма $$$m_{i}$$$ не превосходит $$$2 \cdot 10^5$$$. Гарантируется, что каждая неупорядоченная пара $$$(u, v)$$$ встречается в описании дорог для одной записи не более одного раза.

Выходные данные

Выведите единственное целое число — минимально количество перемещений во времени, чтобы добраться из города $$$1$$$ в город $$$n$$$, или $$$-1$$$, если это невозможно.

Обратите внимание, что перемещение в момент времени $$$a_{1}$$$ тоже считается перемещением.

Примеры
Входные данные
5 2
4
1 2
2 3
3 4
4 5
2
2 3
3 5
6
2 1 2 1 2 1
Выходные данные
5
Входные данные
5 2
3
1 2
3 1
4 3
2
2 1
4 5
5
1 2 1 1 1
Выходные данные
-1
Примечание

В первом примере вы находитесь в городе $$$1$$$ и перемещаетесь в момент $$$a_{1} = 2$$$. Так как подходящих для проезда дорог нет, то вы ничего не делаете и перемещаетесь в момент $$$a_{2} = 1$$$, после чего проезжаете по дороге $$$(1, 2)$$$. Переместившись в момент $$$a_{3} = 2$$$, вы проезжаете по дороге $$$(2, 3)$$$. Переместившись в момент $$$a_{4} = 1$$$, вы останетесь в городе $$$3$$$ и сделаете следующее перемещение во времени. В момент времени $$$a_{5} = 2$$$ вы проедете по дороге $$$(3, 5)$$$ и окажетесь в конечном городе за $$$5$$$ перемещений во времени.

Во втором примере можно показать, что при данных перемещениях во времени добраться до города $$$5$$$ невозможно.