Hints: Zhily and Cycle

Try to forget “cycle” for a moment.
If we output a Hamiltonian cycle as an order $p_1, p_2, \ldots, p_n$, then each vertex $u$ points to exactly one next vertex:

$$ \mathrm{nxt}[u] = \text{the vertex after }u\text{ in the cycle}. $$

So we need a permutation $\mathrm{nxt}$ of $1..n$ such that:

• every value appears exactly once (bijection),
• for every $u$, we have an edge $u \to \mathrm{nxt}[u]$, i.e. $$ \mathrm{nxt}[u] \ge a_u, $$
• and this permutation is one single cycle.

Easier version 1: ignore “single cycle”.
Can you first construct any permutation $\mathrm{nxt}$ with only

$$ \mathrm{nxt}[u] \ge a_u\ \forall u? $$

This is an assignment problem where each row $u$ can choose any value in interval $[a_u, n]$.

For the assignment-only version, sort vertices by decreasing $a_u$.
Also keep available target values as $n, n-1, \ldots, 1$.

Greedy idea: give the largest remaining target to the most restrictive row.

Concrete greedy:

• let ord be vertices sorted by $(a_u\ \text{descending}, u\ \text{descending})$;
• for the $i$-th vertex in this order, assign $$ \mathrm{nxt}[u] = n-i. $$

Feasibility check:

$$ n-i \ge a_u. $$

If this fails for some $u$, no valid permutation exists at all, so answer is No.

Now you have a valid permutation $\mathrm{nxt}$, but maybe with multiple directed cycles (a functional graph decomposition).

Easier version 2: suppose there are exactly two cycles.
How can we merge them while keeping all constraints $\mathrm{nxt}[u] \ge a_u$ true?

Pick one vertex $x$ from cycle 1 and one vertex $y$ from cycle 2.
Current outgoing targets are $\mathrm{nxt}[x]$ and $\mathrm{nxt}[y]$.

If you swap these two targets, the two cycles become one (standard cycle-merge trick in permutations), provided both constraints stay valid:

$$ \mathrm{nxt}[y] \ge a_x,\qquad \mathrm{nxt}[x] \ge a_y. $$

Define interval for each vertex:

$$ I_u = [a_u, \mathrm{nxt}[u]]. $$

The two inequalities from Hint 6 are exactly:

$$ \mathrm{nxt}[y] \in I_x,\quad \mathrm{nxt}[x] \in I_y. $$

A sufficient condition is that intervals overlap and are ordered by left endpoint: if $a_x \le a_y \le \mathrm{nxt}[x]$, then after swapping, both endpoints still lie inside allowed ranges.

Easier version 3: process intervals in increasing left endpoint $a_u$ (and for equal $a_u$, decreasing right endpoint).

Maintain an “active best” interval with maximum current right endpoint (reach).
Whenever a new interval starts after reach, it cannot interact with previous active block, so restart the block.

When a new interval overlaps the active block:

• if its vertex is in a different current cycle, swap outgoing targets between this vertex and best, then those two cycles merge;
• if it is in the same cycle, no merge now, but it may extend reach.

Use DSU over initial cycle IDs to track which cycles are already merged.

Why does one overlap-based swap preserve validity?

Suppose

$$ a_{\mathrm{best}} \le a_u \le \mathrm{nxt}[\mathrm{best}], $$

and intervals are $[a_{\mathrm{best}}, r_b]$, $[a_u, r_u]$.

After swapping rights:

• best gets $r_u$, and $r_u \ge a_u \ge a_{\mathrm{best}}$;
• u gets $r_b$, and overlap gives $r_b \ge a_u$.

So both vertices still satisfy lower bounds.

At the end, if all cycle IDs are in one DSU component, you built one Hamiltonian cycle.

To print it, start from any vertex (the model uses $1$) and repeatedly follow nxt exactly $n$ times.

Complexity target:

• sorting vertices and intervals: $O(n \log n)$,
• building initial cycle IDs: $O(n)$,
• DSU operations and sweep: near-linear.

So per test case it is $O(n \log n)$.