NE(E)RC в предыдущие годы содержал ряд задач, связанных с кактусами - связными неориентированными графами, в которых каждое ребро принадлежит не более чем одному простому циклу. Интуитивно кактус - это обобщение дерева, в котором разрешены некоторые циклы. Традиционный кактус, который изначально использовался в задаче NEERC 2005, показан на втором рисунке в разделе "Примеры".
Вам даны n целых чисел d[1]
, d[2]
, ..., d[n]
. Постройте любой кактус с n вершинами так, чтобы вершина i имела степень d[i]
(то есть ровно d[i]
инцидентных ребер), или определите, что такого кактуса не существует. Мультиребра и петли не допускаются.
В первой строке записано одно целое число n (2 ≤ n ≤ 2000) - количество вершин в кактусе. Вторая строка содержит n целых чисел d[1]
, d[2]
, ..., d[n]
(1 ≤ d[i]
≤ n - 1) - желаемые степени вершины.
Если невозможно построить кактус, удовлетворяющий условиям, выведите -1.
В противном случае по традиции выведите построенный кактус как набор реберно непересекающихся путей.
В первой строке выведите целое число m - количество таких путей. Каждая из следующих m строк должна содержать путь на графе. Путь должен начинаться с целого числа k[i]
(k[i]
≥ 2), за которым следуют k[i]
целых чисел от 1 до n. Эти k[i]
чисел должны представлять последовательные вершины одного пути. Соседние вершины пути должны быть разными. Путь может посещать одну и ту же вершину несколько раз, но каждое ребро кактуса должно быть пройдено ровно один раз во всем выводе.