Восьминіг#8365

Восьминіг

1 секунда

64 мегабайти

Середня

Нещодавно Петрик повернувся додому з відпочинку на морі. Петрик дуже любить тварин, а тому найбільше цей відпочинок запам'ятався йому саме великою кількістю тварин. Серед них був і його найулюбленіший — восьминіг.

Повернувшись додому, Петрик одразу ж захотів побудувати багато восьминогів. Для цього він вирішив використовувати свій конструктор. Конструктор являє собою набір гнучких паличок, якими можна з'єднувати диски. Кожен з $n$ дисків має $a_{i}$ a_i отворів, у які можна вставляти палички. Паличка не може з'єднувати диск із самим собою, а будь-яку пару дисків можна з'єднати не більше ніж однією паличкою.

В уявленні Петрика, восьминіг виглядає наступним чином:

тіло восьминога складається з трьох або більше дисків, з'єднаних по колу паличками;
щупальце восьминога складається з декількох дисків, з'єднаних між собою паличками; щупальце може розгалужуватись, але не може зростатись;
кожне щупальце приєднується до якогось диска у тілі восьминога однією паличкою;

Зверніть увагу, що у восьминога може бути декілька щупалець, а може і не бути жодного щупальця. Ба більше, декілька щупалець можуть бути приєднані до одного диска у тілі. На малюнку показані деякі восьминоги.

Завдання

Допоможіть Петрику скласти восьминогів, щоб виконувалися наступні умови:

для побудови було використано всі диски;
кожен отвір кожного диска був заповнений паличкою;
кількість побудованих восьминогів була максимально можливою. Зверніть увагу, що цей пункт є обов'язковим лише у деяких підзадачах.

Вхідні дані

У першому рядку вхідного файла задано одне число $n$ $(1 \leq n \leq 1 0^{5})$ (1 \le n \le 10^5) — кількість дисків у конструкторі Петрика.

У другому рядку записано $n$ цілих чисел $a_{i}$ a_i $(1 \leq a_{i} < n)$ (1 \le a_i < n) — кількість отворів у $i$ -му диску.

Третій рядок містить одне ціле число $ma x imi z e$ , яке дорівнює $0$ , якщо не потрібно максимізувати кількість восьминогів, і $1$ у протилежному випадку.

Вихідні дані

У першому рядку вихідного файла виведіть «Yes», якщо можна побудувати восьминогів, і «No» — у протилежному випадку. У випадку позитивної відповіді виведіть число $c$ — кількість восьминогів. Далі виведіть $n$ рядків. На $i$ -му з них запишіть два цілих числа $n u m_{i}$ num_i $(1 \leq n u m_{i} \leq c)$ (1 \le num_i \le c), $p_{i}$ p_i — номер восьминога, якому належить диск $i$ , та номер сусіднього диска, який знаходиться ближче до тіла восьминога. Якщо диск $i$ належить тілу, будемо вважати, що $p_{i} = - 1$ p_i = -1.

Для кращого розуміння ознайомтеся з прикладами з умови.

Приклади

Приклад 1

Приклад 2

Приклад 3

Оцінювання

Підзадача	Бали	Додаткові обмеження	Максимізація кількості восьминогів	Необхідні підзадачі
0	0	Тести з умови	Потрібна	-
1	9	Для всіх $i$ виконується $a_{i} \in {1, 3}$ a_i \in \{1, 3\}	Не потрібна	-
2	13	Для всіх $i$ виконується $a_{i} \in {1, 3}$ a_i \in \{1, 3\}	Потрібна	1
3	27	-	Не потрібна	1
4	51	-	Потрібна	0, 1, 2, 3