这是问题的困难版本。简单版本和困难版本之间的唯一区别在于,困难版本要求您构建一个令人满意的树的示例。
作为一名土系法师,雷伊已经掌握了种植树木的咒语!但马纳里亚吹嘘说她可以种植更令人印象深刻的树种。雷记得最稀有的树可以使用某种排列所代表的公式来种植——请帮助她构建它!
给你一个长度为 $$$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$$$ 的边。
您可以在任何情况下输出答案(上限或下限)。例如,字符串“是", "是", "是“,和”是的“将被识别为”是".
示例
输入复制
961 3 4 5 2 643 4 1 254 3 5 1 241 2 3 474 3 5 7 6 2 162 4 6 1 3 532 1 342 4 1 364 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$$$之前。
在第二个示例中,可以证明不存在满足给定约束的树。