Революція кактусів#7603
Advanced Cave Megapolis (ACM) — це місто, яке пережило глобальну ядерну війну і існує у підземних печерах. Печери сполучені між собою переходами, і все місто можна подати у вигляді графа.
У печерному місті почалася революція. Все населення рівномірно поділене на партій, які не можуть дійти згоди щодо прийняття спільних законів. Вирішено поділити місто на районів, у кожному з яких мешканці матимуть змогу встановлювати власні закони.
Дано схему міста у вигляді графа. Ваше завдання — розбити цей граф на районів однакового розміру. Кожен район має бути зв'язним підграфом, тобто підмножиною вершин графа.
Кількість вершин у графі ділиться на , а граф, який представляє місто, — це кактус: зв'язний неорієнтований граф, у якому кожне ребро належить не більше ніж одному простому циклу. Інтуїтивно, кактус — це узагальнення дерева, у якому допускаються деякі цикли.
Нижче подано схему міста з печерами, поділену на райони.
Перший рядок містить три числа , і (1 \le n \le 50\ 000, 0 \le m \le 10\ 000, 1 \le k \le n). Тут — кількість вершин у графі. Вершини пронумеровано від до . Ребра задано як множину реберно-неперетинних шляхів: — кількість таких шляхів, — кількість районів, на які необхідно розбити місто, ділиться на .
Кожен з наступних рядків задає шлях у графі. Шлях починається числом s_i (2 \le s_i \le 1000), після якого наведено s_i чисел від до . Ці s_i чисел позначають вершини графа у шляху. Сусідні вершини у шляху різні. Шлях може проходити через одну й ту ж вершину кілька разів, проте кожне ребро використовується лише один раз. Кратних ребер у графі немає (між будь-якими двома вершинами існує не більше одного ребра).
Граф на вході є кактусом.
Якщо вершини графа можна розбити на районів, виведіть рядків по \frac{n}{k} чисел у кожному. Кожен рядок має містити вершини району у зростаючому порядку.
Якщо рішення не існує, виведіть .
Приклад 1
Приклад 2