Месть кактуса
Месть кактуса
NE(E)RC в предыдущие годы содержал ряд задач, связанных с кактусами - связными неориентированными графами, в которых каждое ребро принадлежит не более чем одному простому циклу. Интуитивно кактус - это обобщение дерева, в котором разрешены некоторые циклы. Традиционный кактус, который изначально использовался в задаче NEERC 2005, показан на втором рисунке в разделе "Примеры".
Вам даны n целых чисел d1
, d2
, ..., dn
. Постройте любой кактус с n вершинами так, чтобы вершина i имела степень di
(то есть ровно di
инцидентных ребер), или определите, что такого кактуса не существует. Мультиребра и петли не допускаются.
Входные данные
В первой строке записано одно целое число n (2 ≤ n ≤ 2000) - количество вершин в кактусе. Вторая строка содержит n целых чисел d1
, d2
, ..., dn
(1 ≤ di
≤ n - 1) - желаемые степени вершины.
Выходные данные
Если невозможно построить кактус, удовлетворяющий условиям, выведите -1.
В противном случае по традиции выведите построенный кактус как набор реберно непересекающихся путей.
В первой строке выведите целое число m - количество таких путей. Каждая из следующих m строк должна содержать путь на графе. Путь должен начинаться с целого числа ki
(ki
≥ 2), за которым следуют ki
целых чисел от 1 до n. Эти ki
чисел должны представлять последовательные вершины одного пути. Соседние вершины пути должны быть разными. Путь может посещать одну и ту же вершину несколько раз, но каждое ребро кактуса должно быть пройдено ровно один раз во всем выводе.
5 2 2 3 2 1
5 2 2 4 2 2 3 2 1 3 2 3 5 2 1 4
4 3 3 2 2
-1
6 1 2 1 1 2 1
-1
15 1 4 3 2 2 2 2 2 4 4 2 2 2 2 2
18 2 9 11 2 9 10 2 2 10 2 2 3 2 3 4 2 2 4 2 5 9 2 5 6 2 6 9 2 7 10 2 7 8 2 8 10 2 1 3 2 11 12 2 12 13 2 13 14 2 14 15 2 2 15