说明

这是一个交互题。

通常，VKOSHP 的参赛者每解决一个问题就会获得一个球，但这一次，每解决一个问题，队伍将获得一棵树！回忆一下，树是一个没有环的连通无向图。

由于比赛中共有 $n$ 个问题，需要准备 $n$ 棵不同的树，每棵树包含 $2n$ 个顶点，编号从 $1$ 到 $2n$。

然而，事实证明树木会不断变化。如果你从某棵树开始，在它被交给解决该问题的队伍之前，可以对这棵树进行不超过 $n - 1$ 次以下操作：

• 选择数字 $a$、$b$、$c$、$d$，使得边 $(a, b)$ 在树中，而边 $(c, d)$ 不在树中；
• 然后，从树中移除边 $(a, b)$ 并添加边 $(c, d)$。保证在此操作后，图仍然是一棵树。

你希望对每个队伍解决的问题进行区分，因此你需要找到 $n$ 棵树，使得即使经过上述修改，它们也能被相互区分。

:::align{center} :::

上图展示了当 $n = 2$ 时测试用例中的“球”的示例。

:::align{center} :::

上面的树展示了你的程序在测试用例中所需输出的树的示例。

这个问题的测试按如下方式组织。首先，你向评测程序提交 $n$ 棵树，每棵树包含 $2n$ 个顶点。

之后，你将会依次收到 $q$ 棵树，每棵树都是通过对你的某棵树应用不超过 $n-1$ 次上述操作得到的。对于每棵树，你必须指明它是由哪一棵原始树派生出来的。

交互协议

首先，你的程序应从标准输入读取两个数字 $n$ 和 $q$（$1 \le n, q \le 100$）。

然后，它应输出 $n$ 棵树，对于每棵树，你需要输出 $2n - 1$ 对数字——该树边的描述。

之后，评测程序将 $q$ 次给你一棵由上述操作得到的树，对于每次查询，你必须输出一个数字 $x$——评测程序给出的这棵树是由哪一棵原始树（的索引）得到的。

2 2






2 3
1 3
4 3

2 3
1 3
1 4

1 2
2 3
3 4
1 4
2 4
1 3



1



2

提示

在样例交互中，评测程序和参赛者程序之间的消息用空行分隔，以便直观显示哪个消息是对哪个消息的响应。在实际交互中，不会有空行，你也不应打印任何空行。

注释

在你的程序每次输出后，输出一个换行符。

在你的程序每次输出后，刷新输出流。

翻译由 DeepSeek 完成