Задача №115170. Путешествия во времени
Берляндия — страна с древней историей, столетиями в ней строились и разрушались дороги. Известно, что в Берляндии всегда было \(n\) городов. Также у вас сохранились записи про \(t\) ключевых моментов в истории страны, пронумерованных от \(1\) до \(t\). Каждая запись содержит список двунаправленных дорог между некоторыми парами городов, по которым можно было перемещаться в Берляндии в конкретный момент времени.
Вы обнаружили машину времени, которая перемещает вас между ключевыми моментами. К сожалению, вы не можете выбирать, куда переместиться, но знаете порядок, состоящий из \(k\) моментов времени \(a_{i}\), в котором машина будет вас перемещать. Так как времени между перемещениями мало, то оказавшись в очередном ключевом моменте времени, вы можете проехать не более чем по одной существующей в тот момент дороге, выходящей из города, в котором вы оказались перед перемещением во времени.
Сейчас вы находитесь в городе \(1\), и машина времени перенесла вас в момент времени \(a_{1}\). Вы хотите как можно быстрее добраться до города \(n\). Определите минимальное количество перемещений во времени, включая первое , которые нужно совершить, чтобы оказаться в городе \(n\).
Первая строка содержит два целых числа \(n\) и \(t\) (\(2 \le n \le 3 \cdot 10^5, 1 \le t \le 3 \cdot 10^5\)) — количество городов в Берляндии и количество записей про ключевые моменты истории. Далее следует описание каждой из \(t\) записей.
Первая строка описания каждой записи содержит одно целое число \(m_{i}\) (\(0 \le m_{i} \le \min \left(\frac{n(n-1)}{2}, 5 \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 5 \cdot 10^5\)) — количество моментов времени, между которыми будут происходить перемещения.
Следующая строка содержит \(k\) целых чисел \(a_1, a_2, \ldots, a_k\) (\(1 \le a_{i} \le t\)) — ключевые моменты времени, в которых вы будете оказываться после каждого перемещения. Ключевые моменты номеруются с \(1\).
Гарантируется, что сумма \(m_{i}\) по всем записям не превосходит \(5 \cdot 10^5\). Гарантируется, что каждая неупорядоченная пара \((u, v)\) встречается в описании дорог для одной записи не более одного раза.
Выведите единственное целое число — минимальное количество перемещений во времени, которе нужно, чтобы добраться из города \(1\) в город \(n\), или \(-1\), если это невозможно.
Обратите внимание, что перемещение в момент времени \(a_{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\) невозможно.
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 3 4 2 2 1 4 5 5 1 2 1 1 1
-1