题目描述

“竟然有平民敢想和我坐在一起。要认清你的身份！”

—— Claire François

这是该问题的困难版本。困难版与简单版的区别在于，困难版要求你构造一个满足条件的树。

作为大地魔法师，Rae 精通种植树木的魔法！但 Manaria 吹嘘自己能种出更稀有的树。Rae 记得，最罕见的树可以用一个特定的排列来生成，请你帮她构造出来！

给定一个长度为 $n$ 的排列 $p$。

请判断是否存在一棵有 $n$ 个结点（编号为 $1,2,\dots,n$）的无向树，满足如下条件：

• 对于所有直接相连的一对结点 $u$、$v$（$1 \leq u < v \leq n$），$u$ 必须在排列 $p$ 中出现在 $v$ 前面。

如果存在，构造出任意一棵符合条件的树。

$^*$一个长度为 $n$ 的排列是一个恰好包含 $1$ 到 $n$ 每个整数各一次的序列，顺序任意。

输入格式

第一行输入一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例组数。

每个测试用例第一行输入一个整数 $n$（$2 \leq n \leq 2 \times 10^5$）。

第二行输入 $n$ 个整数 $p_1,p_2,\dots,p_n$（$1 \leq p_i \leq n$）。保证所有 $p_i$ 两两不同。

保证所有测试用例中 $n$ 的总和不超过 $2\times 10^5$。

输出格式

对于每个测试用例，如果存在满足条件的树，输出一行 “Yes”，否则输出 “No”。

如果答案是 “Yes”，接下来输出 $n-1$ 行，每行两个整数 $u\ v$，表示树中的一条边连接了 $u$ 和 $v$。

你可以用任意大写或小写方式输出答案单词。例如 "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<3$，且 $1$ 在 $p$ 中比 $3$ 先出现，
• $1<4$，且 $1$ 在 $p$ 中比 $4$ 先出现，
• $5<6$，且 $5$ 在 $p$ 中比 $6$ 先出现，
• $2<6$，且 $2$ 在 $p$ 中比 $6$ 先出现，
• $1<6$，且 $1$ 在 $p$ 中比 $6$ 先出现。

在第二个样例中，可以证明不存在满足约束条件的树。

由 ChatGPT 5 翻译

来源

Codeforces 2171F，英文题名 Rae Taylor and Trees (hard version)。