# 交换之后的复原

## 背景故事

实验室的装置可以交换两个身体里的思想，但同一对身体永远不能再次使用装置。实验结束后，两位尚未参与的志愿者帮助大家回到自己的身体。

(本故事由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

### 输入

```text
2 1
1 2
```

### 输出

```text
5
3 1
4 2
3 2
4 1
3 4
```

## 样例 2

### 输入

```text
4 2
1 2
3 4
```

### 输出

```text
8
5 1
6 2
5 2
6 1
5 3
6 4
5 4
6 3
```

## 样例 3

### 输入

```text
1 0
```

### 输出

```text
0
```

## 样例说明

样例 1 的历史只有交换 1、2；给出的五步使用身体 3、4 协助复原，也恢复两位辅助者。样例 2 有两个互不相交的交换，八步后两位辅助者自然归位。样例 3 已经复原，无需操作。输出方案不唯一。

![样例 1：每行给出身体 1、2、3、4 内的思想；五次新增交换后恢复同号。](assets/example.svg)

样例 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 秒。

[特殊评测程序](checker.py) 检查完整交换历史、无序对唯一性、次数上限和所有思想复原，不要求与样例输出逐字一致。

[题解](solution.zh.md) · [测量环境](../../../docs/评测环境与性能.md) · [测量记录](../../../docs/benchmark-R33.json)