Революция кактуса
Революция кактуса
Advanced Cave Megapolis (ACM) является городом, который выживает в подземных пещерах после глобальной ядерной войны. Пещеры соединены между собой переходами и весь город на карте может быть представлена в виде графа.
Сейчас в пещерном городе проходит революция. Все население города равномерно разделено на k партий, которые не могут договориться о принятии общих законов. Они решили разделить свой город на k районов, в каждом из которых граждане имеют право вводить собственные законы, которые им больше нравятся.
Вам задана карта города в виде графа. Вам следует разделить этот граф на k районов одинакового размера. Каждый район должен быть связным подграфом, являющимся подмножеством вершин графа.
К счастью, количество вершин в графе делится на k, а граф представляющий город, является кактусом - связным неориентированным графом, в котором каждое ребро принадлежит не более одному простому циклу. Интуитивно кактус - это обобщение дерева, в котором разрешены некоторые циклы.
Ниже приведена карта города с 15 пещерами, разделенная на 3 района.
Giriş verilənləri
Первая строка содержит три числа 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]
чисел представляют вершины графа в пути.Соседние вершины в пути различны. Путь может проходить по одной вершине несколько раз, однако каждое ребро встречается только один раз. Мультиребера в графе отсутствуют (между любыми двумя вершинами существует не более одного ребра).
Граф в примере является кактусом.
Çıxış verilənləri
Если вершины графа можно разбить на k районов, выведите k строк с n / k числами в каждой. Каждая строка описывает район в виде списка вершин, входящих в него. Номера вершин следует выводить в возрастающем порядке для каждого района.
Если решения не существует, вывести -1.
Nümunə
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
4 5 6 7 8 10 11 12 13 15 1 2 3 9 14
4 2 2 3 1 2 3 2 2 4
-1