交换之后的复原 — 题解¶
采用 Keeler 的双辅助构造；Evans、Huang 与 Nguyen 的论文 讨论了该方法及进一步改进。Codex（GPT-6）负责本题规格、构造的程序化、状态跟踪证明和独立检查器，不将这一已有方法署为原创。
将最终状态分成环¶
先模拟历史，令 \(p[u]\) 表示身体 \(u\) 当前的思想编号。它是一个排列。沿 \(p\) 分解出长度至少为二的环，固定点无需处理。对一个环记为 \(a_1,\ldots,a_t\) ，约定身体 \(a_i\) 内是思想 \(a_{i+1}\) ，最后身体内是思想 \(a_1\) .设辅助身体为 \(x=N+1,y=N+2\) .
对该环依次输出：
- 交换 \((x,a_1)\) .
- 交换 \((y,a_t)\) .
- 对 \(i=2,\ldots,t\) ，依次交换 \((x,a_i)\) .
- 交换 \((y,a_1)\) .
共 \(t+2\) 次。所有环处理完后，若非平凡环数为奇数，再交换 \((x,y)\) 一次。
跟踪每个思想¶
设处理本环前，两个辅助身体内的思想为 \(X,Y\) ，它们可能已互换。第一步后，\(x\) 得到 \(a_2\) ，\(a_1\) 暂存 \(X\) .第二步后，\(y\) 得到 \(a_1\) ，\(a_t\) 暂存 \(Y\) .
第三步开始，\(x\) 每次携带的恰好是下一个目标身体的正确思想；交换后该身体复原，\(x\) 接手下一个思想。最后它把 \(a_t\) 送回，并取走 \(Y\) .第四步把 \(a_1\) 送回，\(y\) 取走 \(X\) .因此本环全部复原，两位辅助者仅互换思想，其他身体未变。最后按奇偶性决定是否交换辅助者，就能全部复原。
合法性、次数与复杂度¶
每一新增交换都涉及辅助身体，所以不会重复历史中的身体对。一个环内的所有对互异；不同环使用不同普通身体；辅助者之间只可能最后交换一次。
设非平凡环数为 \(c\) ，参与这些环的普通身体数为 \(s\) .总次数是 \(s+2c+(c\bmod2)\) .由于每环至少两个身体，\(2c\le s\le N\) ，所以不超过 \(2N+1\) .分解、构造及输出均为 \(O(N+M)\) 时间，保存排列、访问状态和输出用 \(O(N)\) 空间。
std.cpp 按环独立处理，证明与实现都较直接。联合处理多个环 可在 \(c\ge3\) 时减少输出步数，两种方法均满足本题上限。
特殊评测¶
执行 python checker.py input.in contestant.out .检查器用集合记录历史与新增的无序身体对，逐步交换思想，最后检查包括辅助者在内全部复原。它还拒绝错误次数、越界编号、自交换、重复对、缺项和多余记号。返回码零表示接受，一表示拒绝。检查器额外存储全部历史对，因此自身空间是 \(O(N+M)\) .