PROGRAMING PROBLEMS

Монгол улс чадварлаг инженерүүд бэлтгэхэд мөн судалгаа шинжилгээний ажилд асар их хөрөнгө хаясны үр дүнд 2020 онд дэлхийн хамгийн хурдан тээврийн хэрэгсэл болох виртуал-хонгилыг бүтээж чадав. Виртуал-хонгил бүр яг К ширхэг хотуудыг бүгдийг нь хооронд нь холбодог. 1 дугаартай хотоос N дугаартай хот хүрэхэд хамгийн багадаа хичнээн хотоор дамжих хэрэгтэйг тооцоолно уу.
 
Оролт:
            Оролтын эхний мөрөнд сул зайгаар тусгаарлагдсан 3-н эерэг бүхэл тоо байх ба N (1 <= N <= 100 000) нийт хотуудын тоо, K (1 <= K <= 1 000) виртуал-хонгил бүр хэдэн хотыг холбосныг илэрхийлэх тоо, M (1 <= M <= 1 000) нийт ашиглаж байгаа виртуал-хонгилуудын тоо.
            Дараагийн M ширхэг мөр бүрт виртуал-хонгил бүрийн тухай мэдээлэл байх ба энэ нь К ширхэг тооноос бүрдэх буюу эдгээр нь тухайн виртуал-хонгил аль аль хотуудыг хооронд холбосоныг илэрхийлэх хотуудын дугаарууд юм.
 
Гаралт:
            Гаралт нь бодлогын хариу болох ганц тооноос бүрднэ. Хэрэв 1 дугаартай хотоос N дугаартай хотруу очих боломжгүй бол -1 гэж хэвлэ.
 
Жишээнүүд:
 
Оролт:
9 3 5
1 2 3
1 4 5
3 6 7
5 6 7
6 8 9
Гаралт:
4
 
Оролт:
15 8 4
11 12 8 14 13 6 10 7
1 5 8 12 13 6 2 4
10 15 4 5 9 8 14 12
11 12 14 3 5 6 1 13
Гаралт:
3
 
1-р жишээний тайлбайр:
            Боломжтой маршрут нь 1-3-6-9 эсвэл 1-5-6-9.