SP7862 ADV04E - Prisoner of Benda

Daniel 喜欢看电视剧，其中《飞出个未来》是他的最爱。在其中一集中，剧情是这样的： Farnsworth 教授和 Amy 使用了一台新发明交换身体，以便教授可以重温他的青春。而 Amy 想到自己年轻时总是大吃大喝，希望能用教授的瘦弱身体再次享受美食。后来，他们发现无法直接通过这台设备将身体换回来，因为设备无法对同一组身体再次操作。教授建议，他们或许可以通过第三个人的帮助恢复到原来的样子。于是，Bender 和教授（在 Amy 的身体里）交换身体，以便可以在不被识别的情况下实施抢劫。但很快，教授（现在在 Bender 的身体里）也厌倦了这个问题，并加入了机器人马戏团开始冒险生活。 此时 Bender 在 Amy 的身体里被抓到了 Robo-Hungarian 皇帝 Nikolai 的游艇上。当 Bender 解释他是一个与人类交换了身体的机器人时，Nikolai 表示他受够了自己被财富困住，希望过上普通机器人的生活。Bender 诱骗 Nikolai 用一个机器人水桶换了身体，而他则打算用 Nikolai 的身体享受帝王般的生活。可是，他发现 Nikolai 的未婚妻和首席官员正在密谋杀他。最后，在教授和忠于他的 Robo-Hungarian 公民的帮助下，Bender 逃过一劫。 与此同时，当 Leela 认为 Fry 只是因为她的外貌才爱她时，她与 Amy 换了身体，占据了教授的身体。试图让 Leela讨厌他，Fry 和 Dr. Zoidberg 交换了身体。这导致他们在约会时互相厌恶，最后在怪异的身体里和解了。 在过程中，Amy 在 Leela 的身体里暴饮暴食，致使其身体超重。她选择与 Hermes 交换身体，这样继续吃，而 Hermes 则努力减掉 Leela 身体上的多余肥肉。在此过程中，她目睹了 Fry 和 Leela 在教授和 Dr. Zoidberg 的身体中亲热，失去了食欲。同时，Zoidberg 和 Nikolai 在 Fry 和机器水桶的身体中成了朋友，并尝试过着他们的生活，不小心炸毁了他们的公寓。而水桶在 Amy 的身体中，向清洁工 Scruffy 表白，但被拒绝了。最终，两个 Globetrotters，Ethan "Bubblegum" Tate 和 "Sweet" Clyde Dixon，通过数学证明可以用两个额外的身体将每个人的思想恢复到原来的身体，并成功做到了，他们本人则作为多余的补充。 在这道题中，我们需要再现这些步骤。我们考虑已有一定数量的身体交换，要求找到一系列交换操作，使得每个人都能够回到自己的身体中，且最多只使用两个额外的身体。请记住，两个特定的身体只有一次交换机会。

第一行输入一个整数 $t$，表示测试用例的数量。接下来的每个测试用例第一行是两个整数 $n$ 和 $m$，分别表示角色的数量和已经发生的身体交换次数。随后 $m$ 行描述这些交换操作。我们把身体用编号从 1 到 $n$ 标记，每个交换由两个编号 $a, b$ 描述，表示两者发生了一次交换。这些交换记录是按时间顺序排列的。

在输出的第一行打印一个整数，表示需要的交换次数，使所有人回到自己的身体中。接着按执行顺序打印这些交换，每行两个整数表示。格式与输入格式一致。结果可以是任何有效解决方案，但不能使用超过两个额外的身体。这两个额外的身体用编号 $n+1$ 和 $n+2$ 表示。所有交换完成后，这两个额外的身���也应该回到自己的位置。此外，总交换次数不能超过 $3n$ 次。

- $1 \le t \le 100$ - $2 \le n \le 100$ - $0 \le m \le \frac{n(n-1)}{2}$ **本翻译由 AI 自动生成**