Помста кактуса
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] числа повинні представляти послідовні вершини одного шляху. Сусідні вершини шляху повинні бути різними. Шлях може відвідувати одну і ту ж вершину кілька разів, але кожне ребро кактуса повинно бути пройдено рівно один раз у всьому виведенні.
