Masala #HKWJ5QYMRL

Va nihoyat yangi yil kechasi ham yetib keldi. Shu vaqtgacha o'z ishlaringizni professional bajarib Qorboboning ishonchiga kira olganingiz uchun u sizni ham sovg'a tarqatish uchun elflar bilan birga olib ketishga qaror qildi.

Sizga sovg'a tarqatishdagi birinchi vazifa sifatida kichkina konchilar shahridagi bolalarga sovg'alarini yetkazish berildi. Shaharchada N ta uy mavjud, ular bir-biri bilan yo'llar orqali bog'langan. Yangi yil kechasi bo'lgani sababli barcha uylar bo'm-bosh, sababi shaharchada bu yerga yaqin joyda joylashgan kon ishchilari vaqtinchalik, faqat ish vaqtlarida yashashadi. Hozir esa dam olish vaqti bo'lgani uchun ular bu yerda emas.

Faqatgina shaharchaning boshi va oxirida joylashgan 1 va N-uylarda shaharchaning qorovullari oilasi bilan doimiy yashashadi. Sizning vazifangiz shu ikki oila bolalariga sovg'alarini yetkazish va bu ishni iloji boricha tez bajarish.

Sizning elvariangizda butun dunyoning to'liq xaritasi mavjud, lekin bu shaharcha kichkina bo'lgani uchun xarita dasturini yasagan dasturchi elflar tomonidan e'tiborsiz qoldirilgan ekan. Elvariada bu shaharcha xaritasining K xil versiyasi mavjud. Har bir xarita to'g'ri yo'llarni ko'rsatadi, lekin to'liq emas. Elvariadagi xarita ilovasida xaritaning K xil versiyasidan faqat bittasini saqlash mumkin, boshqa versiyasini yuklab olish uchun 1 daqiqa vaqt kerak bo'ladi, sababi shaharchada internet tarmog'i sekin. Xaritaning yangi versiyasi yuklab olingandan so'ng eski versiyasi o'chib ketadi.

Dastlab elvariangizda shaharcha xaritalarining birortasi yuklab olinmagan va shaharchadagi 1-uyda turgan bo'lsangiz N-uyga yetib borish uchun minimal qancha vaqtni xarita yuklab olish uchun sarflashingiz kerak bo'ladi?

Birinchi qatorda \(N\) va \(K\) sonlari, shaharchadagi uylar soni va xaritalar soni. \(1 \leq N,K \leq 2000\).

Keyingi qatorlarda \(K\) ta xarita ma'lumotlari quyidagi formatda beriladi: i-xarita ma'lumotining 1-qatorida \(C_i\) soni - i-xaritadagi yo'llar soni beriladi. Keyingi \(C_i\) ta qatorning har birida ikkitadan natural son a va b \((1 \leq a,b \leq N, a \neq b)\) sonlari beriladi, bu sonlar i-xaritadagi a va b uylar orasida yo'l borligini bildiradi. Barcha \(K\) ta xaritadagi yo'llar soni \(2*10^5\) tadan oshmaydi.

Xarita yuklab olish uchun sarflanadigan minimal vaqtni chop eting. Agar N-uyga yetib borishning iloji bo'lmasa -1 chiqaring.