一个研究财团正在建造一个新的数据中心。在数据中心中，一组计算机被设置在一起，通过网络进行协作和通信。该网络仅通过计算机之间的直接双向链路工作。在他们成功构建了“名称保留网络”（name-preserving networks）之后，他们决定进行其他具有保证属性的设计。

财团要求你提交一份“环保留网络”（ring-preserving network）的设计。我们将网络的“环”定义为网络中所有计算机的一种排序，使得排序中任意两台相邻的计算机之间都有直接链路，且排序中的第一台和最后一台计算机之间也存在直接链路。

环保留网络是一种网络设计，即使在丢失了原始计算机标识的情况下，也能高效地找到其自身的一个环。你需要提交几个环保留的网络设计。

为了评估你的网络设计，研究财团建立了一个自动化程序。你将被要求提供网络设计，指定计算机的确切数量 $C$ 和它必须包含的双向链路的确切数量 $L$。你必须为每台计算机分配一个 $1$ 到 $C$ 之间的唯一 ID，并使用这些 ID 来列出链路的端点。评估程序将接收该设计，并返回一份经过以下更改的网络设计副本：

• 唯一 ID 已被均匀随机置换（即，每个 ID 现在出现在任何一台计算机上的概率相等），
• 每条链路都按 ID 从小到大的顺序排列（使用新的 ID），并且
• 链路集合按第一个端点的递增顺序排列（使用新的 ID），若第一个端点相同，则按第二个端点从小到大排列（即字典序）。

你需要能够找到修改后网络的一个环。它不需要是原始的环。

输入格式

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

首先，你的程序应该读取包含一个整数 $T$ 的单行，表示测试用例的数量。然后，必须处理 $T$ 个测试用例。

对于每个测试用例，你的程序必须首先读取包含两个整数 $C$ 和 $L$ 的一行：网络设计中包含的计算机数量和链路数量。

然后，你需要创建一个包含 $C$ 台计算机和 $L$ 条链路的网络设计，并打印恰好 $L$ 行来表示该设计。这些行中的每一行必须包含两个整数 $A$ 和 $B$，表示计算机 $A$ 和 $B$ 之间的一条不同链路，其中 $A \neq B$。注意，如果你列出了链路 $A\ B$，则不能再次列出 $A\ B$ 或 $B\ A$。

在读取你的网络设计后，评测机将向你发送 $L$ 行，表示置换后的设计。这些行中的第 $i$ 行包含两个整数 $U_i$ 和 $V_i$，表示具有新 ID $U_i$ 和 $V_i$ 的计算机之间的双向链路。该副本是使用从所有可能的排列中均匀随机选择的排列生成的，且独立于任何其他选择。

输出格式

为了完成一个测试用例，你需要向评测机发送一行包含 $C$ 个整数 $x_1, x_2, \dots, x_C$ 的内容，表示置换后设计的一个环。也就是说，评测机发回的链路集合必须包含 $\{x_1, x_C\}$ 或 $\{x_C, x_1\}$，并且对于所有 $i$，它必须包含 $\{x_i, x_{i+1}\}$ 或 $\{x_{i+1}, x_i\}$。

在解决所有测试用例后，你不应向评测机发送额外信息。换句话说，如果你的程序在为最后一个测试用例打印完 $x$ 列表后继续向标准输出打印内容，你将收到“答案错误”（Wrong Answer）的判决。

如果评测机在任何时候读取到你程序的格式错误输入（错误的标记数量、非整数标记或超出范围的数字），它将立即停止并判定为“答案错误”。然而，如果你的程序在等待评测机的输入，它可能会超过时间限制并收到“超出时间限制”（Time Limit Exceeded）的判决。另一方面，如果你提交了一个可恢复的错误（通过网络发送重复的连接、从计算机到自身的连接，或者发送一个重复了某台计算机的环，或者使用了在置换版本中不存在的边），评测机将继续与你的程序通信以尝试完成，但最终判决将是“答案错误”。

注意，只要该设计符合两种情况的所有限制，你就可以为不同的测试用例提交相同的网络设计。此外，评测机中随机生成的种子是固定的，因此以相同的顺序发送相同的一组原始网络设计将得到相同的一组副本。

数据范围

时间限制：30 秒。 内存限制：2 GB。 $1 \le T \le 100$。 $3 \le C \le 10000$。 $C \le L \le C \times (C - 1)/2$。 $1 \le U_i < V_i \le C$，对于所有 $i$。 $U_i \le U_{i+1}$，对于所有 $i$。 如果 $U_i = U_{i+1}$，则 $V_i \le V_{i+1}$，对于所有 $i$。 存在长度为 $C$ 的排列 $f$ 和长度为 $L$ 的排列 $g$，使得对于每个 $i$，如果 $\{A, B\}$ 是你原始设计中的第 $g(i)$ 行，则 $\{U_i, V_i\} = \{f(A), f(B)\}$。（给定的链路是通过将计算机 ID 的排列应用于你给出的 ID，然后按字典序对链路进行排序而产生的）。

子任务

子任务 1（可见判决） $L \le C + 10$。

子任务 2（隐藏判决） $L \le 20000$。

说明

你可以使用测试工具在本地或我们的平台上进行测试。要在本地测试，你需要将该工具与你的代码并行运行；你可以使用我们的交互式运行器（interactive runner）来实现。有关更多信息，请阅读该文件中的注释，并查看 FAQ 中的“交互式问题”部分。测试工具的说明包含在工具的注释中。我们鼓励你添加自己的测试用例。请注意，虽然测试工具旨在模拟评测系统，但它不是真实的评测系统，其行为可能有所不同。如果你的代码通过了测试工具但未通过真实评测，请检查 FAQ 的“编程”部分，确保你使用的编译器与我们相同。