CF2247E.Build a Tree

You are given two integers $n$ and $k$.

Construct a tree$^{\text{∗}}$ with $n$ vertices such that $\sum\limits_{i = 1}^{n} \operatorname{dist}(i, (i \bmod n) + 1) = k$$^{\text{†}}$, or determine that no such tree exists.

$^{\text{∗}}$A tree is a connected graph without cycles.

$^{\text{†}}$$\operatorname{dist}(i, j)$ is the number of edges on the shortest path from vertex $i$ to vertex $j$ in the tree.

给你两个整数 $n$ 和 $k$。

请构造一棵包含 $n$ 个顶点的树$^{\text{∗}}$，使得 $\sum\limits_{i = 1}^{n} \operatorname{dist}(i, (i \bmod n) + 1) = k$$^{\text{†}}$；若不存在这样的树，则判定其不存在。

$^{\text{∗}}$树是一类无环的连通图。

$^{\text{†}}$$\operatorname{dist}(i, j)$ 表示该树中从顶点 $i$ 到顶点 $j$ 的最短路径所包含的边数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The only line of each test case contains two integers $n$ and $k$ ($2 \le n \le 2 \cdot 10^5$, $0 \le k \le n^2$) — the number of vertices in the tree and the required value of $k$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是测试用例的描述。

每个测试用例仅一行，包含两个整数 $n$ 和 $k$（$2 \le n \le 2 \cdot 10^5$，$0 \le k \le n^2$）——分别为树中顶点的数量和所需的 $k$ 值。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, if there is no solution, output $-1$.

Otherwise, output $n - 1$ lines. Each line should contain two integers $u$ and $v$ ($1 \le u, v \le n$), denoting an edge of the tree. The edges may be output in any order.

If there are multiple suitable trees, output any of them.

对于每个测试用例，若无解，则输出 $-1$。

否则，输出 $n - 1$ 行。每行应包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示树中的一条边。边的输出顺序可以任意。

若存在多个满足条件的树，输出其中任意一个即可。

In the first example, the tree consists of the single edge $(1, 2)$. Therefore, $\operatorname{dist}(1, 2) + \operatorname{dist}(2, 1) = 1 + 1 = 2$.

In the second example, one possible tree is shown below.

For this tree, $\operatorname{dist}(1, 2) + \operatorname{dist}(2, 3) + \operatorname{dist}(3, 4) + \operatorname{dist}(4, 1) = 1 + 2 + 2 + 1 = 6$.

In the fourth example, it can be shown that no suitable tree exists.

在第一个例子中，树仅包含一条边 $(1, 2)$。因此，$\operatorname{dist}(1, 2) + \operatorname{dist}(2, 1) = 1 + 1 = 2$。

在第二个例子中，一棵可能的树如下所示。

对于该树，$\operatorname{dist}(1, 2) + \operatorname{dist}(2, 3) + \operatorname{dist}(3, 4) + \operatorname{dist}(4, 1) = 1 + 2 + 2 + 1 = 6$。

在第四个例子中，可以证明不存在满足条件的树。