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.

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 $ .

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.

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.