Революція кактуса
Advanced Cave Megapolis (ACM) — це місто, яке вижило в підземних печерах після глобальної ядерної війни. Печери з'єднані між собою переходами, і все місто на карті можна представити у вигляді графа.
У печерному місті зараз відбувається революція. Все населення міста рівномірно поділено на k партій, які не можуть дійти згоди щодо прийняття спільних законів. Вони вирішили поділити своє місто на k районів, у кожному з яких громадяни мають право вводити власні закони, які їм більше подобаються.
Вам надано карту міста у вигляді графа. Ваше завдання — розділити цей граф на k районів однакового розміру. Кожен район повинен бути зв'язним підграфом, що є підмножиною вершин графа.
На щастя, кількість вершин у графі ділиться на k, а граф, що представляє місто, є кактусом — зв'язним неорієнтованим графом, у якому кожне ребро належить не більше ніж одному простому циклу. Інтуїтивно кактус — це узагальнення дерева, в якому дозволені деякі цикли.
Нижче наведена карта міста з 15 печерами, розділена на 3 райони.
Вхідні дані
Перший рядок містить три числа n, m і k (1 ≤ n ≤ 50 000, 0 ≤ m ≤ 10 000, 1 ≤ k ≤ n). Тут n — кількість вершин у графі. Вершини пронумеровані від 1 до n. Ребра задані множиною реберно-неперетинних шляхів, де m — число таких шляхів, k — кількість районів, на яке слід розбити місто, n ділиться на k.
Кожен з наступних m рядків містить шлях у графі. Шлях починається числом s[i] (2 ≤ s[i] ≤ 1000), за яким слідують s[i] чисел від 1 до n. Ці s[i] числа представляють вершини графа в шляху. Сусідні вершини в шляху різні. Шлях може проходити по одній вершині кілька разів, однак кожне ребро зустрічається тільки один раз. Мультиребра в графі відсутні (між будь-якими двома вершинами існує не більше одного ребра).
Граф у прикладі є кактусом.
Вихідні дані
Якщо вершини графа можна розбити на k районів, виведіть k рядків з n / k числами в кожному. Кожен рядок описує район у вигляді списку вершин, що входять до нього. Номери вершин слід виводити у зростаючому порядку для кожного району.
Якщо розв'язку не існує, виведіть -1.