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

Месть кактуса

Месть кактуса

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

NE(E)RC в предыдущие годы содержал ряд задач, связанных с кактусами - связными неориентированными графами, в которых каждое ребро принадлежит не более чем одному простому циклу. Интуитивно кактус - это обобщение дерева, в котором разрешены некоторые циклы. Традиционный кактус, который изначально использовался в задаче NEERC 2005, показан на втором рисунке в разделе "Примеры".

Вам даны n целых чисел d[1], d[2], ..., d[n]. Постройте любой кактус с n вершинами так, чтобы вершина i имела степень d[i] (то есть ровно d[i] инцидентных ребер), или определите, что такого кактуса не существует. Мультиребра и петли не допускаются.

Giriş verilənləri

В первой строке записано одно целое число n (2n2000) - количество вершин в кактусе. Вторая строка содержит n целых чисел d[1], d[2], ..., d[n] (1d[i]n - 1) - желаемые степени вершины.

Çıxış verilənləri

Если невозможно построить кактус, удовлетворяющий условиям, выведите -1.

В противном случае по традиции выведите построенный кактус как набор реберно непересекающихся путей.

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

prb9582.gif

Nümunə

Giriş verilənləri #1
5
2 2 3 2 1
Çıxış verilənləri #1
5
2 2 4
2 2 3
2 1 3
2 3 5
2 1 4
Giriş verilənləri #2
4
3 3 2 2
Çıxış verilənləri #2
-1
Giriş verilənləri #3
6
1 2 1 1 2 1
Çıxış verilənləri #3
-1
Giriş verilənləri #4
15
1 4 3 2 2 2 2 2 4 4 2 2 2 2 2
Çıxış verilənləri #4
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
Mənbə 2019 ACM NEERC, Полуфинал, Декабрь 1, Задача C