Берляндия — страна с древней историей, столетиями в ней строились и разрушались дороги. Известно, что в Берляндии всегда было \(n\) городов. Также у вас сохранились записи про \(t\) ключевых моментов в истории страны, пронумерованных от \(1\) до \(t\). Каждая запись содержит список двунаправленных дорог между некоторым парами городов, по которым можно было перемещаться в Берляндии в конкретный момент времени.
Вы обнаружили машину времени, которая перемещает вас между ключевыми моментами. К сожалению, вы не можете выбирать, в какой момент времени переместиться, но знаете порядок, состоящий из \(k\) моментов времени \(a_{i}\), в котором машина будет вас перемещать. Так как времени между перемещениями мало, то оказавшись в очередном ключевом моменте времени (в том числе после последнего перемещения во времени), вы можете проехать не более чем по одной существующей в данный момент времени дороге, выходящей из города, в котором вы оказались перед перемещением во времени.
Сейчас вы находитесь в городе \(1\), и машина времени уже перенесла вас в момент времени \(a_{1}\). Вы хотите как можно быстрее добраться до города \(n\). Определите минимальное количество перемещений во времени, включая первое, которые нужно совершить, чтобы оказаться в городе \(n\).
Выходные данные
Выведите единственное целое число — минимально количество перемещений во времени, чтобы добраться из города \(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\) невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
|
2
|
5 2
3
1 2
3 1
4 3
2
2 1
4 5
5
1 2 1 1 1
|
-1
|