Начинающий сталкер получил задание добраться до склада в промзоне. Он нашел в электронном архиве несколько карт территории промзоны. Так как карты составлялись разными людьми, то на каждой из них есть информация только о некоторых дорогах промзоны. Одна и та же дорога может присутствовать на нескольких картах.

В пути сталкер может загружать из архива на мобильный телефон по одной карте. При загрузке новой карты предыдущая в памяти телефона не сохраняется. Сталкер может перемещаться лишь по дорогам, отмеченным на карте, загруженной на данный момент. Каждая загрузка карты стоит 1 рубль. Для минимизации расходов сталкеру нужно выбрать такой маршрут, чтобы как можно меньшее число раз загружать карты. Сталкер может загружать одну и ту же карту несколько раз, при этом придется заплатить за каждую загрузку. Изначально в памяти мобильного телефона нет никакой карты.

Требуется написать программу, которая вычисляет минимальную сумму расходов, необходимую сталкеру, чтобы добраться от входа в промзону до склада.

В первой строке входного файла находятся два натуральных числа N и K (2 ≤ N ≤ 2000; 1 ≤ K ≤ 2000) - количество зданий промзоны и количество карт соответственно. Вход в промзону находится в здании с номером 1, а склад - в здании с номером N.

В последующих строках находится информация об имеющихся картах. Первая строка описания i-ой карты содержит число r_i - количество дорог, обозначенных на i-ой карте. Затем идут r_i строк, содержащие по два натуральных числа a и b (1 ≤ a, b ≤ N; a ≠ b), означающих наличие на i-ой карте дороги, соединяющей здания a и b. Суммарное количество дорог, обозначенных на всех картах, не превышает 300 000 (r₁ + r₂ + ... + r_K ≤ 300 000).

В выходной файл необходимо вывести одно число - минимальную сумму расходов сталкера. В случае, если до склада добраться невозможно, выведите число -1.

Начинающий сталкер получил задание добраться до склада в промзоне. Он нашел в электронном архиве несколько карт территории промзоны. Так как карты составлялись разными людьми, то на каждой из них есть информация только о некоторых дорогах промзоны. Одна и та же дорога может присутствовать на нескольких картах.

В пути сталкер может загружать из архива на мобильный телефон по одной карте. При загрузке новой карты предыдущая в памяти телефона не сохраняется. Сталкер может перемещаться лишь по дорогам, отмеченным на карте, загруженной на данный момент. Каждая загрузка карты стоит 1 рубль. Для минимизации расходов сталкеру нужно выбрать такой маршрут, чтобы как можно меньшее число раз загружать карты. Сталкер может загружать одну и ту же карту несколько раз, при этом придется заплатить за каждую загрузку. Изначально в памяти мобильного телефона нет никакой карты.

Требуется написать программу, которая вычисляет минимальную сумму расходов, необходимую сталкеру, чтобы добраться от входа в промзону до склада.

В первой строке входного файла находятся два натуральных числа N и K (2 ≤ N ≤ 2000; 1 ≤ K ≤ 2000) - количество зданий промзоны и количество карт соответственно. Вход в промзону находится в здании с номером 1, а склад - в здании с номером N.

В последующих строках находится информация об имеющихся картах. Первая строка описания i-ой карты содержит число r_i - количество дорог, обозначенных на i-ой карте. Затем идут r_i строк, содержащие по два натуральных числа a и b (1 ≤ a, b ≤ N; a ≠ b), означающих наличие на i-ой карте дороги, соединяющей здания a и b. Суммарное количество дорог, обозначенных на всех картах, не превышает 300 000 (r₁ + r₂ + ... + r_K ≤ 300 000).

В выходной файл необходимо вывести одно число - минимальную сумму расходов сталкера. В случае, если до склада добраться невозможно, выведите число -1.