Masala #JTIDOWYORJ

Bir kuni, "Russia Code Cup" tadbirida musobaqadan tashqari musobaqa sifatida futbol o'ynashga qaror qilindi. Barcha ishtirokchilar n ta jamoaga bo'lingan va bir nechta o'yin o'tkazishgan, ikkita jamoa bir-biriga qarshi bir necha marta o'ynay olmaydi.

Tayinlangan sudya eng tajribali a'zo - Pavel edi. Lekin u hammadan dono bo'lgani uchun tez orada o'yindan zerikib uxlab qoldi. Uyg'onib, u turnir tugaganini va jamoalar barcha o'yinlar natijalarini bilishni xohlashlarini aniqladi.

Pavel hech kim uning uxlab yotgani va natijalarga e'tibor bermasligi haqida bilishini istamadi, shuning uchun u barcha o'yinlar natijalarini tiklashga qaror qildi. Buning uchun u barcha jamoalardan so'radi va haqiqiy g'olib do'stlik ekanligini, ya'ni har bir jamoa boshqa jamoalarni to'liq k marta mag'lub etishini bilib oldi. Pavelga barcha shartlarga javob beradigan turnirning xronologiyasini topishga yordam bering yoki aks holda bunday jadval yo'qligini xabar qiling.

Birinchi qatorda ikkita butun son mavjud - n va k\( ( 1 ≤  n ,  k  ≤ 1000 )\).

Birinchi qatorda m butun sonini chop eting - o'ynalgan o'yinlar soni. Keyingi m satrda barcha mosliklar haqidagi ma'lumotlar bo'lishi kerak, har bir satrda bittadan mos keladi. i -chi qatorda ikkita butun a[i] va b[i] ( 1 ≤  a[i] ,  b[i]  ≤  n ; a[i]  ≠  b[i] ) boʻlishi kerak . a [i] va b i raqamlari shuni anglatadiki, i -o'yinda a[i] raqamiga ega bo'lgan jamoa b[i] raqamli jamoaga qarshi g'alaba qozongan. Siz taxmin qilishingiz mumkin, jamoalar 1 dan n gacha raqamlangan.

Agar muammoning shartlariga javob beradigan turnir mavjud bo'lmasa, u holda -1 ni chop eting.