Kaktus inqilabı

Advanced Cave Megapolis (ACM) qlobal nüvə müharibəsindən sonra yeraltı mağaralarda yaşayan bir şəhərdir. Mağaralar bir-birinə keçidlər vasitəsilə bağlıdır və şəhərin xəritəsi qraf şəklində təqdim oluna bilər.

Hal-hazırda mağara şəhərində inqilab baş verir. Şəhərin bütün əhalisi k partiyaya bərabər şəkildə bölünüb və onlar ümumi qanunların qəbulunda razılığa gələ bilmirlər. Onlar şəhərlərini k rayona bölməyə qərar veriblər ki, hər bir vətəndaş özlərinə daha çox uyğun gələn qanunları tətbiq edə bilsin.

Sizə şəhərin xəritəsi qraf şəklində verilir. Siz bu qrafı eyni ölçüdə k rayona bölməlisiniz. Hər bir rayon qrafın zirvələrinin alt çoxluğu olan əlaqəli alt qraf olmalıdır.

Xoşbəxtlikdən, qrafın zirvələrinin sayı k-ya bölünür və şəhəri təmsil edən qraf kaktusdur - hər bir kənarın ən çox bir sadə dövrəyə aid olduğu əlaqəli istiqamətsiz qraf. İntuisiya ilə kaktus bəzi dövrələrin icazə verildiyi ağacın ümumiləşdirilməsidir.

Aşağıda 15 mağara ilə şəhərin 3 rayona bölünmüş xəritəsi verilmişdir.

Giriş məlumatları

Birinci sətir n, m və k (1 ≤ n ≤ 50 000, 0 ≤ m ≤ 10 000, 1 ≤ k ≤ n) üç ədədini ehtiva edir. Burada n qrafın zirvələrinin sayıdır. Zirvələr 1-dən n-ə qədər nömrələnmişdir. Kənarlar kənarlarla kəsişməyən yollar çoxluğu ilə verilir, burada m belə yolların sayıdır, k şəhərin bölünməli olduğu rayonların sayıdır, n k-ya bölünür.

Növbəti m sətirin hər biri qrafda bir yolu ehtiva edir. Yol s[i] (2 ≤ s[i] ≤ 1000) ədədi ilə başlayır, ardınca 1-dən n-ə qədər olan s[i] ədədləri gəlir. Bu s[i] ədədləri yoldakı qrafın zirvələrini təmsil edir. Yoldakı qonşu zirvələr fərqlidir. Yol bir zirvədən bir neçə dəfə keçə bilər, lakin hər bir kənar yalnız bir dəfə rast gəlinir. Qrafda çoxkənarlar yoxdur (hər hansı iki zirvə arasında ən çox bir kənar mövcuddur).

Misaldakı qraf kaktusdur.

Çıxış məlumatları

Əgər qrafın zirvələrini k rayona bölmək mümkündürsə, hər birində n / k ədəd olan k sətir çıxarın. Hər bir sətir rayonu təşkil edən zirvələrin siyahısı şəklində təsvir edir. Hər bir rayon üçün zirvələrin nömrələrini artan qaydada çıxarın.

Əgər həll mövcud deyilsə, -1 çıxarın.