У місті \(Н\) за нез'ясованих обставин територія одного із заводів перетворилася на аномальну зону. Усі під'їзди до території було перекрито, а сама вона отримала назву промзони. У промзоні знаходяться \(N\) будівель, деякі з них з'єднані дорогами. Будь-якою дорогою можна переміщатися в обох напрямках.

Початківець сталкер отримав завдання дістатися до складу в промзоні. Він знайшов у електронному архіві кілька карток території промзони. Так як карти складалися різними людьми, то на кожній з них є інформація лише про деякі дороги промзони. Одна й та сама дорога може бути присутня на декількох картах. На шляху сталкер може завантажувати з архіву на мобільний телефон по одній карті. Під час завантаження нової картки попередня карта у пам'яті телефону не зберігається. Сталкер може переміщатися лише дорогами, зазначеними на карті, яка завантажена на даний момент. Кожне завантаження картки коштує 1 гривню. Для мінімізації витрат сталкеру потрібно вибрати такий маршрут, щоб якнайменше разів завантажувати карти. Сталкер може завантажувати ту саму карту кілька разів, при цьому доведеться заплатити за кожне завантаження. Спочатку в пам'яті мобільного телефону немає карти.

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

Формат вхідних даних

У першому рядку вхідних даних містяться два натуральні числа \(N\) і \(K\) (\(2 ≤ N ≤ 2000\); \(1 ≤ K ≤ 2000\)) — кількість будівель промзони та кількість карт відповідно. Вхід до промзони знаходиться в будівлі з номером 1, а склад — у будівлі з номером \(N\).

У наступних рядках міститься інформація про наявні картки. Перший рядок опису \(i\)-ої карти містить число \(r_i\) - кількість доріг, позначених на \(i\)-ій карті.

Потім йдуть рядки, що містять по два натуральні числа \(a\) і \(b\) (\(1 ≤ a, b ≤ N\); \(a ≠ b\)), що означають наявність на \(i\)-ій карті дороги, що з'єднує будівлі \(a\) і \(b\). Сумарна кількість доріг, позначених на всіх картах, не перевищує 300 000 (\(r_1+r_2+...+r_K ≤ 300 000\)).

Формат вихідних даних

Виведіть одне число - мінімальну суму витрат сталкера. Якщо до складу дістатися неможливо, виведіть число –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