← 返回题目列表

Codeforces · 2171/F

F. 雷·泰勒和树木(硬版)

中文机器翻译题面 查看原题
“没想到一个平民竟然能理解坐在我旁边。知道你的位置!”
— 克莱尔·弗朗索瓦

这是问题的困难版本。简单版本和困难版本之间的唯一区别在于,困难版本要求您构建一个令人满意的树的示例。

作为一名土系法师,雷伊已经掌握了种植树木的咒语!但马纳里亚吹嘘说她可以种植更令人印象深刻的树种。雷记得最稀有的树可以使用某种排列所代表的公式来种植——请帮助她构建它!

给你一个长度为 $$$n$$$ 的排列$$$^{\text{*}}$$$ $$$p$$$。

判断是否存在一棵无向树,其顶点为$$$n$$$,标记为$$$1, 2, \dots, n$$$,满足以下条件:

  • 令 $$$u$$$ 和 $$$v$$$ ($$$1\leq {\color{red}{u \lt v}} \leq n$$$) 为由边连接的任意两个顶点。那么$$$u$$$ 出现在$$$p$$$ 中的$$$v$$$ 之前。

另外,如果存在这样的树,则输出其中的任何一个。

$$$^{\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$$$。

输出

对于每个测试用例,在单行上输出“是“如果存在满足给定条件的树,并且”No”否则。

那么,如果答案是“是",输出 $$$n-1$$$ 行。这些行中的第 $$$i$$$ 应该包含两个整数 $$$u$$$ 和 $$$v$$$,表示连接顶点 $$$u$$$ 和 $$$v$$$ 的边。

您可以在任何情况下输出答案(上限或下限)。例如,字符串“是", "是", "是“,和”是的“将被识别为”是".

示例

输入
复制

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$$$ 出现在 $$$p$$$ 中的 $$$3$$$ 之前,
  • $$$1 \lt 4$$$,且 $$$1$$$ 出现在 $$$p$$$ 中的 $$$4$$$ 之前,
  • $$$5 \lt 6$$$,并且 $$$5$$$ 出现在 $$$p$$$ 中的 $$$6$$$ 之前,
  • $$$2 \lt 6$$$,且 $$$2$$$ 出现在 $$$p$$$ 中的 $$$6$$$ 之前,
  • $$$1 \lt 6$$$,并且$$$1$$$出现在$$$p$$$中的$$$6$$$之前。

在第二个示例中,可以证明不存在满足给定约束的树。