Description

一个研究联盟正在建设一个新的数据中心。在数据中心中，一组计算机通过网络相互连接和通信。该网络仅通过计算机之间的直接双向链路工作。在他们成功开发了名称保持网络后，决定开发其他具有保证特性的设计。

该联盟要求你提交一种环保持网络的设计方案。我们将网络的环定义为网络中所有计算机的一个排列顺序，使得排列中任意两个相邻计算机之间存在直接链路，且排列的首尾计算机之间也存在直接链路。

环保持网络是一种网络设计方案，即使在丢失原始计算机标识后，仍能高效找到自身的环。你需要提交多个满足环保持特性的网络设计。

为了评估你的网络设计，研究联盟设置了一个自动化程序。你需要根据指定的计算机数量 $\mathbf{C}$ 和双向链路数量 $\mathbf{L}$ 提交网络设计。你必须为每台计算机分配一个 1 到 $\mathbf{C}$ 之间的唯一 ID，并用这些 ID 列出 $\mathbf{L}$ 条链路。评估程序会接收该设计，并返回一个经过以下修改的网络设计副本：

• 唯一 ID 被均匀随机排列（即每个新 ID 可能出现在任意计算机上），
• 每条链路按新 ID 从小到大排列，
• 链路集合按第一个端点的升序排列（使用新 ID），若第一个端点相同则按第二个端点的升序排列（即字典序）。

你需要能够从修改后的网络中找到至少一个环。这个环不需要是原始环。

交互协议

这是一个交互式问题。请确保你已阅读我们 FAQ 中关于交互式问题的部分。

最初，你的程序应读取一个整数 $\mathbf{T}$，表示测试用例的数量。然后，需要处理 $\mathbf{T}$ 个测试用例。

对于每个测试用例，你的程序首先读取一行包含两个整数 $\mathbf{C}$ 和 $\mathbf{L}$，分别表示网络设计中的计算机数量和链路数量。

然后，你需要创建一个包含 $\mathbf{C}$ 台计算机和 $\mathbf{L}$ 条链路的网络设计，并打印恰好 $\mathbf{L}$ 行表示该设计。每行包含两个不同的整数 $\mathrm{A}$ 和 $\mathrm{B}$，表示计算机 $\mathrm{A}$ 和 $\mathrm{B}$ 之间的一条链路（$A \neq B$）。注意，如果你列出了链路 $\mathrm{A} \mathrm{B}$，就不能再列出 $\mathrm{A} \mathrm{B}$ 或 $\mathrm{B} \mathrm{A}$。

在读取你的网络设计后，评测系统会返回 $\mathbf{L}$ 行表示经过排列的设计。第 $i$ 行包含两个整数 $\mathbf{U}_{\mathbf{i}}$ 和 $\mathbf{V}_{\mathbf{i}}$，表示新 ID 为 $\mathbf{U}_{\mathbf{i}}$ 和 $\mathbf{V}_{\mathbf{i}}$ 的计算机之间的双向链路。该副本使用从所有可能排列中均匀随机选择的排列生成，且与其他选择独立。

要完成一个测试用例，你需要向评测系统发送一行包含 $\mathbf{C}$ 个整数 $x_{1}, x_{2}, \ldots, x_{\mathbf{C}}$，表示排列后设计中的一个环。即，评测系统返回的链路集合中必须包含 $x_{1} x_{\mathbf{C}}$ 或 $x_{\mathbf{C}} x_{1}$，并且对于所有 $i$，必须包含 $x_{i} x_{i+1}$ 或 $x_{i+1} x_{i}$。

在处理完所有测试用例后，你不应再向评测系统发送任何信息。换句话说，如果在打印最后一个测试用例的环列表后，你的程序继续向标准输出打印内容，将被判为错误答案。

如果在任何时候评测系统从你的程序中读取到格式错误的输入（令牌数量错误、非整数令牌或超出范围的数字），它将立即停止并判定为错误答案。然而，如果你的程序在等待评测系统的输入时超时，可能会被判为超出时间限制。另一方面，如果你犯了一个可恢复的错误（发送的网络中包含重复连接、自环连接，或发送的环中重复使用计算机或使用了排列后版本中不存在的边），评测系统会继续与你的程序通信以完成测试，但最终判定仍为错误答案。

请注意，你可以在不同的测试用例中提交相同的网络设计，只要该设计同时满足所有限制条件。此外，评测系统中的随机生成种子是固定的，因此以相同顺序提交相同的原始网络设计集将获得相同的副本集。

Input Format

参见交互协议。

Output Format

参见交互协议。

2
4 5





1 2
1 3
1 4
2 4
3 4

4 4




1 2
1 3
2 4
3 4

1 2
1 3
4 2
4 3
1 4





1 2 4 2

1 2
1 4
3 2
3 4




2 1 3 4

Hint

样例解释

第一组样例是错误的，第二组样例是正确的，因此最后的评判为 Wrong Answer。

限制

• $1 \leq \mathbf{T} \leq 100$。
• $3 \leq \mathbf{C} \leq 10000$。
• $\mathbf{C} \leq \mathbf{L} \leq \mathbf{C} \times (\mathbf{C} - 1) / 2$。
• 对于所有 $i$，$1 \leq \mathbf{U}_{\mathbf{i}} < \mathbf{V}_{\mathbf{i}} \leq \mathbf{C}$。
• 对于所有 $i$，$\mathbf{U}_{\mathbf{i}} \leq \mathbf{U}_{\mathbf{i+1}}$。
• 如果 $\mathbf{U}_{\mathbf{i}} = \mathbf{U}_{\mathbf{i+1}}$，则对于所有 $i$，$\mathbf{V}_{\mathbf{i}} \leq \mathbf{V}_{\mathbf{i+1}}$。
• 存在长度为 $\mathbf{C}$ 的排列 $f$ 和长度为 $\mathbf{L}$ 的排列 $g$，使得对于每个 $i$，如果 $A \ B$ 是你的原始设计中的第 $g(i)$ 行，则 $\{\mathbf{U}_{\mathbf{i}}, \mathbf{V}_{\mathbf{i}}\} = \{f(A), f(B)\}$。（给定的链路是通过对计算机 ID 进行排列并对链路按字典序排序后得到的）。

测试集 1（5 分，可见评测结果）

• $\mathbf{L} \leq \mathbf{C} + 10$。

测试集 2（17 分，隐藏评测结果）

• $\mathbf{L} \leq 20000$。

翻译由 DeepSeek V3 完成