eolymp
bolt
Try our new interface for solving problems
Məsələlər

Революция кактуса

Революция кактуса

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 122 MiB

Advanced Cave Megapolis (ACM) является городом, который выживает в подземных пещерах после глобальной ядерной войны. Пещеры соединены между собой переходами и весь город на карте может быть представлена в виде графа.

Сейчас в пещерном городе проходит революция. Все население города равномерно разделено на k партий, которые не могут договориться о принятии общих законов. Они решили разделить свой город на k районов, в каждом из которых граждане имеют право вводить собственные законы, которые им больше нравятся.

Вам задана карта города в виде графа. Вам следует разделить этот граф на k районов одинакового размера. Каждый район должен быть связным подграфом, являющимся подмножеством вершин графа.

К счастью, количество вершин в графе делится на k, а граф представляющий город, является кактусом - связным неориентированным графом, в котором каждое ребро принадлежит не более одному простому циклу. Интуитивно кактус - это обобщение дерева, в котором разрешены некоторые циклы.

Ниже приведена карта города с 15 пещерами, разделенная на 3 района.

prb7603.gif

Giriş verilənləri

Первая строка содержит три числа n, m и k (1n50 000, 0m10 000, 1kn). Здесь n - количество вершин в графе. Вершины пронумерованы от 1 до n. Ребра заданы множеством реберно - непересекающихся путей, где m число таких путей, k - количество районов, на которое следует разбить город, n делится на k.

Каждая из следующих m строк содержит путь в графе. Путь начинается числом s[i] (2s[i]1000), за которым следуют s[i] чисел от 1 до n. Эти s[i] чисел представляют вершины графа в пути.Соседние вершины в пути различны. Путь может проходить по одной вершине несколько раз, однако каждое ребро встречается только один раз. Мультиребера в графе отсутствуют (между любыми двумя вершинами существует не более одного ребра).

Граф в примере является кактусом.

Çıxış verilənləri

Если вершины графа можно разбить на k районов, выведите k строк с n / k числами в каждой. Каждая строка описывает район в виде списка вершин, входящих в него. Номера вершин следует выводить в возрастающем порядке для каждого района.

Если решения не существует, вывести -1.

Nümunə

Giriş verilənləri #1
15 3 3
9 1 2 3 4 5 6 7 8 3
7 2 9 10 11 12 13 10
5 2 14 9 15 10
Çıxış verilənləri #1
4 5 6 7 8
10 11 12 13 15
1 2 3 9 14
Giriş verilənləri #2
4 2 2
3 1 2 3
2 2 4
Çıxış verilənləri #2
-1
Mənbə 2010 ACM NEERC, Semifinals, November 24, Problem C