Восьминiг
Нещодавно Петрик повернувся додому з вiдпочинку на морi. Петрик дуже любить тварин, а тому бiльш за все цей вiдпочинок запам’ятався йому саме їх великою кiлькiстю. Серед них була i його найулюбленiша — восьминiг.
Повернувшись додому, Петрик одразу ж захотів побудувати багато восьминогів. Для цього він вирішив використовувати свій конструктор. Конструктор являє собою набір гнучких паличок, якими можна з’єднувати диски. Кожен з n дисків має a[i] отворів, у які можна вставляти палички. Паличка не може з’єднувати диск з самим собою та будь-яку пару дисків може з’єднувати не більше однієї палички.
В уявленні Петрика, восьминіг виглядає наступним чином
• тіло восьминога складається с трьох або більше дисків, з’єднаних по колу паличками;
• щупальце восьминога складається з декількох дисків, з’єднаних між собою паличками; щупальце може розгалужуватись та не може зростатись;
• кожне щупальце приєднується до якогось диску у тілі восьминога однією паличкою;
Зверніть увагу, що у восьминога може бути декілька щупалець, а може і навпаки не бути жодного щупальця. Більш того, декілька щупалець можуть бути приєднані до одного диска у тілі. На малюнку показані деякі восьминоги.
####Завдання
Допоможіть Петрику скласти восьминогів, щоб виконувались наступні умови:
• для побудови були використані усі диски;
• кожен отвір кожного диску був заповнений паличкою;
• кількість побудваних восьминогів була б максимально можливою. Зверніть увагу, що цей пункт є обов'язковим тільки у деяких підзадачах.
Вхідні дані У першому рядку вхідного файла задано одне число n (1 ≤ n ≤ 10^5) - кількість дисків у конструкторі Петрика.
У другому рядку записано n цілих чисел a[i] (1 ≤ a[i] < n) - кількість отворів у i-му диску.
Третій рядок містить одне ціле число maximize, яке дорівнює 0, якщо не треба максимізувати кількість восьминогів, і 1 в противному випадку.
Вихідні дані У перший рядок вихідного файлу виведіть «Yes», якщо можна побудувати восьминогів, i «No» в противному випадку. У випадку позитивної відповіді виведіть число c - кількість восьминогів. Далі виведіть n рядків. На i-му з них запишіть два цілих числа num[i] (1 ≤ num[i] ≤ c), p[i] - номер восьминога, якому належить диск i, та номер сусіднього диску, який знаходиться ближче до тіла восьминога. Якщо диск i належить тілу, будемо вважати, що p[i] = -1.
Для кращого розуміння ознайомтесь з прикладами із умови.
####Оцінювання
Пiдзадача Бали Додатковi обмеження Максимiзацiя кiлькостi Необхідні підзадачівосьминогiв
0 0 Тести з умови Потрібна -
1 9 Для усiх i виконується ai Не потрібна -∈ {1, 3}
2 13 Для усiх i виконується ai Потрібна 1∈ {1, 3}
3 27 - Не потрібна 1
4 51 - Потрібна 0, 1, 2, 3