P12965 [GCJ Farewell Round #4] Ring-Preserving Networks

一个研究联盟正在建设一个新的数据中心。在数据中心中，一组计算机通过网络相互连接和通信。该网络仅通过计算机之间的直接双向链路工作。在他们成功开发了**名称保持网络**后，决定开发其他具有保证特性的设计。 该联盟要求你提交一种**环保持网络**的设计方案。我们将网络的**环**定义为网络中所有计算机的一个排列顺序，使得排列中任意两个相邻计算机之间存在直接链路，且排列的首尾计算机之间也存在直接链路。 **环保持网络**是一种网络设计方案，即使在丢失原始计算机标识后，仍能高效找到自身的环。你需要提交多个满足环保持特性的网络设计。 为了评估你的网络设计，研究联盟设置了一个自动化程序。你需要根据指定的计算机数量 $\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}$。 在处理完所有测试用例后，你不应再向评测系统发送任何信息。换句话说，如果在打印最后一个测试用例的环列表后，你的程序继续向标准输出打印内容，将被判为错误答案。 如果在任何时候评测系统从你的程序中读取到格式错误的输入（令牌数量错误、非整数令牌或超出范围的数字），它将立即停止并判定为错误答案。然而，如果你的程序在等待评测系统的输入时超时，可能会被判为超出时间限制。另一方面，如果你犯了一个可恢复的错误（发送的网络中包含重复连接、自环连接，或发送的环中重复使用计算机或使用了排列后版本中不存在的边），评测系统会继续与你的程序通信以完成测试，但最终判定仍为错误答案。 请注意，你可以在不同的测试用例中提交相同的网络设计，只要该设计同时满足所有限制条件。此外，评测系统中的随机生成种子是固定的，因此以相同顺序提交相同的原始网络设计集将获得相同的副本集。

参见交互协议。

参见交互协议。

**样例解释** 第一组样例是错误的，第二组样例是正确的，因此最后的评判为 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 完成