CF2223D Zhily and Cycle

Zhily 和 Jily 决心环游世界，消除所有混乱。他们从某地出发，希望恰好访问每一个区域一次。 给定一个有向图，包含 $n$ 个编号 $1$ 到 $n$ 的顶点。对于每一个顶点 $i$（$1 \le i \le n$），存在从 $i$ 指向所有满足 $a_i \le j \le n$ 的顶点 $j$ 的有向边。 请找到该图的一个哈密尔顿回路$^{\text{∗}}$。 $^{\text{∗}}$ 哈密尔顿回路是指恰好访问每个顶点一次的回路。

每个测试点包含多组测试数据。第一行为测试用例个数 $t$（$1 \le t \le 10^4$）。接下来的 $t$ 组数据，每组输入格式如下： 每组的第一行包含一个整数 $n$ ($1 \leq n \leq 10^5$)，表示顶点数量。 第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$（$1 \leq a_i \leq n$），描述图中边的情况。 保证所有测试点的 $n$ 之和不超过 $10^6$。

对于每组测试数据，如果不存在哈密尔顿回路，输出一行 “No”。 否则，先输出一行 “Yes”。在下一行输出一个 $p_1, p_2, \dots, p_n$ 的排列（$1\le p_i\le n$），表示回路访问顶点的顺序。如果有多组答案，输出其中任意一组均可。 输出时不区分大小写。例如，“yEs”、“yes”、“Yes” 和 “YES” 均视为肯定回答。

在第一个测试样例中，下方图示展示了一条哈密尔顿回路：$1 \to 7 \to 5 \to 2 \to 4 \to 3 \to 6 \to 1$。  在第二个测试样例中，不存在哈密尔顿回路，因为没有指向顶点 $1$ 的入边（即，没有顶点能够到达顶点 $1$）。 由 ChatGPT 5 翻译