Editorial: Zhily and Cycle

If we output a Hamiltonian cycle as

define

Then $\mathrm{nxt}$ is a permutation of $1..n$.
The graph rule says an edge $u \to v$ exists iff $v \ge a_u$, so constraints become:

So we need a permutation $\mathrm{nxt}$ such that:

1. $\mathrm{nxt}$ is bijective (every target used exactly once),
2. $\mathrm{nxt}[u] \ge a_u$ for all $u$,
3. the permutation consists of exactly one cycle.

This viewpoint makes the solution natural: first satisfy 1 and 2, then enforce 3.

Ignore the “single cycle” condition for now.

We need to assign each row $u$ one distinct value from interval $[a_u, n]$.
This is a lower-bounded permutation assignment.

Sort vertices by descending $a_u$ (if tie, descending index).
Call this order ord[0..n-1].

Assign

Interpretation: the most restrictive row (largest $a_u$) gets the largest remaining value.

If at some step

then impossible.

Reason: we already fixed $i$ rows with the largest lower bounds, so only values $1..(n-i)$ remain for current and future rows.
Current row needs at least $a_{\mathrm{ord}[i]} > n-i$, impossible now and impossible in any arrangement.

If this check never fails, we obtained a valid bijection with all lower bounds satisfied.

So after this phase:

• either we already know answer is No,
• or we have a valid permutation $\mathrm{nxt}$ (but maybe multiple cycles).

A permutation decomposes into disjoint directed cycles.

Suppose $x$ and $y$ are vertices from different cycles.
Current outgoing edges:

If we swap these two outgoing targets:

the two cycles merge into one (standard permutation fact), provided constraints remain valid:

So the key is: when is such a safe swap guaranteed?

For each vertex $u$, define

Since $\mathrm{nxt}[u] \ge a_u$, this interval is nonempty.

If we swap rights of vertices $x$ and $y$, validity after swap is exactly:

A very useful sufficient condition:

• $a_x \le a_y \le \mathrm{nxt}[x]$ (so $I_x$ reaches the start of $I_y$),
• then swapping right endpoints keeps both rows valid.

This is why overlap structure of intervals drives the whole algorithm.

Create records $(l, r, u)$ where

Sort by:

1. increasing $l$,
2. for equal $l$, decreasing $r$.

Now sweep left to right, maintaining:

• best: a vertex in the current overlap block,
• reach: maximum right endpoint currently represented by best.

If next interval starts after reach, it cannot overlap current block, so start a new block.

If it overlaps (l \le reach), then this interval can safely interact (swap) with best.

Use the greedy assignment from Easier Version 1.
If feasibility check fails, print No.

Traverse permutation $\mathrm{nxt}$ and assign each vertex a cycle ID cid[u].
Let number of cycles be cycles.

Initialize DSU with cycles components.
comps = cycles.

For each sorted interval belonging to vertex $u$:

• If it starts a new disjoint block, set best=u, reach=nxt[u].
• Else it overlaps current block:
  • If DSU roots of cid[best] and cid[u] differ:
    • swap nxt[best] and nxt[u],
    • union DSU roots,
    • decrement comps.
  • Update (best, reach) to keep a representative with maximal right endpoint.

Suppose current best has interval $[a_b, r_b]$ and new $u$ has $[a_u, r_u]$ with

After swap:

• best gets $r_u$, valid because $r_u \ge a_u \ge a_b$;
• u gets $r_b$, valid because $r_b \ge a_u$.

So lower-bound constraints are preserved.

Every successful swap across two different DSU sets merges two permutation cycles into one larger cycle.
If after sweep comps = 1, permutation is one cycle, hence Hamiltonian cycle exists.
If comps > 1, no further safe merges are available under this interval sweep structure, so answer is No.

1. Greedy phase gives a valid bijection iff any valid bijection exists.
2. Every performed swap preserves $\mathrm{nxt}[u] \ge a_u$ for affected vertices.
3. Swap between different cycles reduces number of cycles by exactly $1$.
4. DSU tracks which original cycles are already connected by swaps.
5. If DSU ends with one component, final permutation is a single cycle and respects all edges.

Thus algorithm outputs Yes with a correct Hamiltonian cycle exactly when it can construct one.

Per test case:

• sorting vertices for greedy: $O(n \log n)$,
• cycle labeling: $O(n)$,
• sorting intervals: $O(n \log n)$,
• DSU operations: near-linear.

Total:

per test case, with overall $n$ sum up to $10^6$ across tests.

When answer is Yes, the model prints:

1. 1,
2. then repeatedly v = nxt[v] for $n$ steps.

Because final permutation is one cycle, this visits every vertex exactly once and returns to start.