В городе Н при невыясненных обстоятельствах территория одного из заводов превратилась в аномальную зону. Все подъезды к территории были перекрыты, а сама она получила название промзоны. В промзоне находятся
N зданий, некоторые из них соединены дорогами. По любой дороге можно перемещаться в обоих направлениях.
Начинающий сталкер получил задание добраться до склада в промзоне. Он нашел в электронном архиве несколько карт территории промзоны. Так как карты составлялись разными людьми, то на каждой из них есть информация только о некоторых дорогах промзоны. Одна и та же дорога может присутствовать на нескольких картах.
В пути сталкер может загружать из архива на мобильный телефон по одной карте. При загрузке новой карты предыдущая в памяти телефона не сохраняется. Сталкер может перемещаться лишь по дорогам, отмеченным на карте, загруженной на данный момент. Каждая загрузка карты стоит 1 рубль. Для минимизации расходов сталкеру нужно выбрать такой маршрут, чтобы как можно меньшее число раз загружать карты. Сталкер может загружать одну и ту же карту несколько раз, при этом придется заплатить за каждую загрузку. Изначально в памяти мобильного телефона нет никакой карты.
Требуется написать программу, которая вычисляет минимальную сумму расходов, необходимую сталкеру, чтобы добраться от входа в промзону до склада.
Входные данные:
- в первой строке входных данных содержатся два натуральных числа
N и
K (
\(2 <= N <= 2000\);
\(1 <= K <= 2000\)) — количество зданий промзоны и количество карт соответственно. Вход в промзону находится в здании с номером
1, а склад — в здании с номером
N.
- в последующих строках находится информация об имеющихся картах. Первая строка описания
i-ой карты содержит число
ri — количество дорог, обозначенных на
i-ой карте;
- затем идут
ri строк, содержащие по два натуральных числа
a и
b (
\(1 <= a\),
\(b <= N\);
\(a ? b\)), означающих наличие на
i-ой карте дороги, соединяющей здания
a и
b. Суммарное количество дорог, обозначенных на всех картах, не превышает 300 000 (
\(r_1 + r_2 + … + r_K <= 300 000\)).
Выходные данные: выведите одно число — минимальную сумму расходов сталкера. В случае, если до склада добраться невозможно, выведите число
–1.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
12 4
4
1 6
2 4
7 9
10 12
3
1 4
7 11
3 6
3
2 5
4 11
8 9
5
3 10
10 7
7 2
12 3
5 12 |
3 |