V-Sort

Treat each position as a vertex, and each allowed swap as an undirected edge. Edge swaps allow arbitrary rearrangement within a connected component. Sorting is therefore possible exactly when each component's current multiset equals its target multiset. Both positions $A_i,B_i$ have target value $i$.

• Subtask 1 ($X=Y=0$): only $A_i$ and $B_i$ can be swapped. Both target values are , so every position must already be correct. Check this in time.

If $X=N$ or $Y=N$, the corresponding edge type is absent. Check isolated vertices too. Since values may repeat, comparing sums alone is insufficient. Total time for the full solution is $O(\sum N)$. All index and frequency magnitudes are at most $1\,000\,000$, so no arithmetic beyond signed 64-bit is required.

Solution written by GPT