CF402C.Searching for Graph

Let's call an undirected graph of n vertices p-interesting, if the following conditions fulfill:

• the graph contains exactly 2_n_ + p edges;
• the graph doesn't contain self-loops and multiple edges;
• for any integer k (1 ≤ k ≤ n), any subgraph consisting of k vertices contains at most 2_k_ + p edges.

A subgraph of a graph is some set of the graph vertices and some set of the graph edges. At that, the set of edges must meet the condition: both ends of each edge from the set must belong to the chosen set of vertices.

Your task is to find a p-interesting graph consisting of n vertices.

我们称一个包含 $n$ 个顶点的无向图为 $p$-有趣图，当且仅当满足以下条件：

• 该图恰好包含 $2n + p$ 条边；
• 该图不含自环和重边；
• 对任意整数 $k$（其中 $1 \leq k \leq n$），由任意 $k$ 个顶点构成的任意子图至多包含 $2k + p$ 条边。

图的一个子图是指图中某些顶点的集合以及某些边的集合；其中边的集合需满足：每条边的两个端点都必须属于所选的顶点集合。

你的任务是构造一个由 $n$ 个顶点组成的 $p$-有趣图。

The first line contains a single integer t (1 ≤ t ≤ 5) — the number of tests in the input. Next t lines each contains two space-separated integers: n, p (5 ≤ n ≤ 24; p ≥ 0; ) — the number of vertices in the graph and the interest value for the appropriate test.

It is guaranteed that the required graph exists.

第一行包含一个整数 $t$（$1 \leq t \leq 5$）—— 输入中测试用例的数量。接下来的 $t$ 行，每行包含两个以空格分隔的整数：$n$、$p$（$5 \leq n \leq 24$；$p \geq 0$；）—— 分别表示图中顶点的数量以及对应测试用例的兴趣值。

保证所要求的图一定存在。

For each of the t tests print 2_n_ + p lines containing the description of the edges of a p-interesting graph: the i-th line must contain two space-separated integers a__i, b__i (1 ≤ a__i, b__i ≤ n; a__i ≠ b__i) — two vertices, connected by an edge in the resulting graph. Consider the graph vertices numbered with integers from 1 to n.

Print the answers to the tests in the order the tests occur in the input. If there are multiple solutions, you can print any of them.

对于每个测试用例，输出 $2n + p$ 行，每行描述一个 $p$-interesting 图中的一条边：第 $i$ 行必须包含两个以空格分隔的整数 $a_i,\ b_i$（满足 $1 \leq a_i,\ b_i \leq n$；且 $a_i \neq b_i$），表示图中连接顶点 $a_i$ 与 $b_i$ 的一条边。图的顶点编号为 $1$ 到 $n$ 的整数。

请按照输入中测试用例出现的顺序输出对应答案。若存在多种可行解，输出任意一种即可。