F. Рей Тейлор и деревья (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное отличие между легкой и сложной версиями заключается в том, что сложная версия просит вас построить пример удовлетворительного дерева.

Как маг Земли, Рэй овладела заклинанием роста деревьев! Но Манария хвастается, что она может вырастить более впечатляющий вид деревьев. Рэй помнит, что самый редкий тип дерева можно вырастить, используя формулу, представленную определенной перестановкой — пожалуйста, помогите ей построить его!

Вам дана перестановка$$$^{\text{∗}}$$$ $$$p$$$ длины $$$n$$$.

Определите, существует ли неориентированное дерево с $$$n$$$ вершинами, пронумерованными $$$1, 2, \dots, n$$$, удовлетворяющее следующему условию:

  • Пусть $$$u$$$ и $$$v$$$ ($$$1\leq {\color{red}{u \lt v}} \leq n$$$) будут любыми двумя вершинами, соединенными ребром. Тогда $$$u$$$ появляется перед $$$v$$$ в $$$p$$$.

Кроме того, если такое дерево существует, выведите любое из них.

$$$^{\text{∗}}$$$Перестановка длины $$$n$$$ — это массив, который содержит каждое целое число от $$$1$$$ до $$$n$$$ ровно один раз, в любом порядке.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$)  — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2\leq n\leq 2\cdot 10^5$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел, $$$p_1, p_2, \dots, p_n$$$ ($$$1\leq p_i\leq n$$$). Гарантируется, что все $$$p_i$$$ различны.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите в одной строке «Yes», если существует дерево, удовлетворяющее данному условию, и «No» в противном случае.

Затем, если ответ «Yes», выведите $$$n-1$$$ строк. $$$i$$$-я из этих строк должна содержать два целых числа $$$u$$$ и $$$v$$$, обозначающих ребро, соединяющее вершины $$$u$$$ и $$$v$$$.

Вы можете выводить ответ в любом регистре (верхнем или нижнем). Например, строки «yEs», «yes», «YES» и «yeS» будут распознаны как «Yes».

Пример
Входные данные
9
6
1 3 4 5 2 6
4
3 4 1 2
5
4 3 5 1 2
4
1 2 3 4
7
4 3 5 7 6 2 1
6
2 4 6 1 3 5
3
2 1 3
4
2 4 1 3
6
4 2 6 5 1 3
Выходные данные
Yes
3 1
4 1
6 5
6 2
6 1
No
No
Yes
2 1
4 3
4 1
No
Yes
4 2
6 2
3 1
5 1
5 2
Yes
3 2
3 1
Yes
4 2
3 1
3 2
Yes
6 4
6 2
3 1
5 4
2 3
Примечание

В первом примере мы можем построить дерево, данное в образце вывода. Мы имеем, что

  • $$$1 \lt 3$$$, и $$$1$$$ появляется перед $$$3$$$ в $$$p$$$,
  • $$$1 \lt 4$$$, и $$$1$$$ появляется перед $$$4$$$ в $$$p$$$,
  • $$$5 \lt 6$$$, и $$$5$$$ появляется перед $$$6$$$ в $$$p$$$,
  • $$$2 \lt 6$$$, и $$$2$$$ появляется перед $$$6$$$ в $$$p$$$,
  • $$$1 \lt 6$$$, и $$$1$$$ появляется перед $$$6$$$ в $$$p$$$.

Во втором примере можно показать, что не существует дерева, удовлетворяющего данным ограничениям.