交换之后的复原¶
背景故事¶
实验室的装置可以交换两个身体里的思想，但同一对身体永远不能再次使用装置。实验结束后，两位尚未参与的志愿者帮助大家回到自己的身体。
(本故事由GPT-6重写)
形式化问题描述¶
有 \(N\) 个身体和 \(N\) 个思想，均编号为 \(1,\ldots,N\) ，最初思想 \(i\) 在身体 \(i\) 内。按输入顺序执行 \(M\) 次历史交换，每次交换给定两个身体当前容纳的思想。历史中没有重复的无序身体对。
现在允许使用两个辅助身体 \(N+1,N+2\) ，最初各容纳同号思想，且没有参与任何历史交换。构造不超过 \(2N+1\) 次新增交换，使全部 \(N+2\) 个思想最终都位于同号身体。
任意一对不同身体在历史和新增交换合起来最多出现一次；无论顺序如何，交换 \((u,v)\) 与 \((v,u)\) 算同一对。允许不使用辅助者或输出零次。保证存在符合上限的方案，输出任意一种即可。本题要求满足给定上限，不要求最少交换次数或最少辅助身体数。
输入格式¶
第一行 N M .接下来 \(M\) 行，每行两个整数 u v 表示历史交换。
输出格式¶
第一行输出新增次数 \(S\) ，随后 \(S\) 行，每行输出新增交换的身体编号 u v .
样例 1¶
输入¶
2 1
1 2
输出¶
5
3 1
4 2
3 2
4 1
3 4
样例 2¶
输入¶
4 2
1 2
3 4
输出¶
8
5 1
6 2
5 2
6 1
5 3
6 4
5 4
6 3
样例 3¶
输入¶
1 0
输出¶
0
样例说明¶
样例 1 的历史只有交换 1、2；给出的五步使用身体 3、4 协助复原，也恢复两位辅助者。样例 2 有两个互不相交的交换，八步后两位辅助者自然归位。样例 3 已经复原，无需操作。输出方案不唯一。
样例 1：每行给出身体 1、2、3、4 内的思想；五次新增交换后恢复同号。
数据范围与分组¶
\(1\le N\le2\times10^5\) ，\(0\le M\le2\times10^5\) ，历史端点在 \([1,N]\) 内、互不相同，且无序对不重复。
规格由 Codex（GPT-6）重新设计：将任务定为使用两个辅助身体、至多 \(2N+1\) 步的构造，补齐格式、范围和合法性规则。
| 分值 | 额外条件 |
|---|---|
| 20% | \(N\le8,\ M\le20\) |
| 30% | \(N,M\le2000\) |
| 50% | 无额外条件 |
资源限制¶
时间 0.5 秒；内存 128 MiB。时限为标准程序每例五次测量的最慢中位数乘以 2，向上取整到 0.5 秒。
特殊评测程序 检查完整交换历史、无序对唯一性、次数上限和所有思想复原，不要求与样例输出逐字一致。