当前没有测试数据。

C. Divine Tree

题目描述

Harshith 在一棵神圣之树下修行，悟得了算法竞赛的真谛。神圣之树是一棵有 $n$ 个节点的有根树，节点编号为 $1 \sim n$。

节点 $v$ 的神圣值 $d(v)$ 被定义为：从根节点到节点 $v$ 的唯一简单路径上，编号最小的节点的编号。

Aryan 是一名求知若渴的算法竞赛选手，他向 Harshith 请教。Harshith 提出了一个条件：给定两个正整数 $n$ 和 $m$，Aryan 需要构造一棵 $n$ 个节点的神圣之树，满足所有节点的神圣值之和为 $m$，即

如果不存在这样的树，则需要判定为无解。

Aryan 向你求助，请你帮他完成这个任务。

补充定义：

• 树：无环连通图。
• 有根树：指定一个特殊节点为根的树。

输入格式

第一行输入一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

对于每个测试用例，输入一行两个整数 $n,m$（$1 \le n \le 10^6$，$1 \le m \le 10^{12}$）。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

对于每个测试用例：

• 若无解，输出 -1。
• 若有解，先输出一行一个整数 $k$，表示树的根节点编号。 接下来输出 $n-1$ 行，每行两个整数 $u_i,v_i$，表示树的一条边（$1 \le u_i,v_i \le n$ 且 $u_i \ne v_i$）。 边的顺序和每条边的两个端点顺序可以任意。 若存在多解，输出任意一种合法方案即可。

样例输入

2
1 2
4 6

样例输出

-1
3
3 1
1 2
2 4

样例解释

• 第一个测试用例：只有一个节点，其神圣值只能是 $1$，和为 $2$ 不可能，故输出 -1。
• 第二个测试用例：以 $3$ 为根的树满足条件，所有节点的神圣值之和为 $6$。

数据范围

• $1 \le t \le 10^4$
• $1 \le n \le 10^6$
• $1 \le m \le 10^{12}$
• 所有测试用例的 $n$ 之和不超过 $10^6$