Problem C: 鸡⽖传说中的宝藏(2024-T3)

Memory Limit：128 MB Time Limit：1.000 S

Judge Style：Text Compare Creator：

Submit：2 Solved：1

在⼀个遥远的国度，有⼀个神秘的传说，关于⼀座隐藏在深⼭⽼林中的神秘宝藏。传说中，只有那些能

够解开鸡⽖之谜的勇者才能找到这个宝藏。

据说，宝藏所在的⽼林中隐藏着许多神奇的鸡⽖形状的地形。这些鸡⽖形状的地形是⼀种迷宫，构成了

前往宝藏的通道。勇者们必须最⼤限度地利⽤鸡⽖的形状，才能找到正确的路径，并在通道中避免陷⼊

困境。

为了解开鸡⽖之谜，勇者们被赋予了⼀项任务：使⽤给定的边，构建⼀个简单⽆向图，以最⼤化图中的

鸡⽖数。他们需要巧妙地选择边的顶点连接⽅式，以形成尽可能多的鸡⽖形状。

只有当勇者们成功构建出鸡⽖数量最多的图形时，他们才能获得通向宝藏的线索。但是，解开鸡⽖之谜

并不容易，因为他们必须在给定的边限制下，选择正确的连接⽅式。

现在，你作为⼀名勇者，接受了这个挑战。你必须聪明地选择边的连接⽅式，以构建出鸡⽖数量最多的

图形，找到通向宝藏的线索。

该图为⼀个鸡⽖的示例,加粗部分被认为在当前鸡⽖中

⼀个鸡⽖是由 4 个部分组成，⼀个点与三个与该点相邻的边，三个边的另⼀端点被认为不在鸡⽖中。

⼀个图上的鸡⽖数是该图最多成形成⼏个鸡⽖，使得图上每个点与边最多在⼀个鸡⽖中。

现在给你 n 条边，你可以使⽤任意个点，构造⼀个简单⽆向图（没有⾃环重边），要求最⼤化该图的鸡

⽖数，并输出n条边的两端点。如果有多解，请让输出的 2n 个数字在⾏优先遍历的顺序下，字典序最

⼩。

这⾥⾏优先遍历的顺序是指：假如说我们最后输出的答案为

1 2

1 3

1 4

那么我们按⾏优先遍历的顺序得到的答案序列为 {1, 2, 1, 3, 1, 4}。

字典序：序列 A 的字典序⼩于序列 B，当且仅当存在 i (1 ≤ i ≤ n)，使得 Ai < Bi ，且对任意的 j (1 ≤ j < i)，Aj = Bj 。

准备好了吗？穿越⽼林的鸡⽖之谜正等待着你的解密。带上你的勇⽓和智慧，踏上这段充满挑战的旅程吧！

第⼀⾏为⼀个整数 T(1 ≤ T ≤ 2 × 10⁵) ，表示测试样例个数。

每个样例⼀⾏，为⼀个整数 n(1 ≤ n ≤ 2 × 10⁵)。保证所有样例的n的和≤ 2 × 10⁵。

每个样例输出 n ⾏，每⾏两个正整数，表示该⽆向边连接的两个顶点（顶点从 1 开始编号）

2
3
5

信奥-比赛