← 返回题目列表

Codeforces · 402/C

C. 搜索图表

中文机器翻译题面 查看原题

如果满足以下条件,我们将 n 个顶点的无向图称为 p-interesting:

- 该图恰好包含 2n + p 条边;
- 该图不包含自环和多重边;
- 对于任何整数 k (1 ≤ k ≤ n),任何由 k 个顶点组成的子图最多包含 2k + p 条边。

图的子图是图顶点的某些集合和图边的某些集合。此时,边集必须满足条件:该集中的每条边的两端必须属于所选的顶点集。

你的任务是找到一个由 n 个顶点组成的 p 有趣图。

输入

第一行包含一个整数 t (1 ≤ t ≤ 5) — 输入中的测试数量。接下来的 t 行每行包含两个空格分隔的整数: n, p (5 ≤ n ≤ 24; p ≥ 0; $$2n + p \leq \frac{n(n-1)}{2}$$) — 图中的顶点数和适当测试的兴趣值。

保证所需的图存在。

输出

对于每个 t 测试,打印 2n + p 行,其中包含 p 个有趣图的边的描述:第 i 行必须包含两个空格分隔的整数 ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — 两个顶点,由结果图中的边连接。考虑用 1 到 n 的整数编号的图顶点。

按照输入中测试发生的顺序打印测试的答案。如果有多个解决方案,您可以打印其中任何一个。

示例

输入 #1

1
6 0

输出 #1

1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6