Harshith 通过在神树下的训练获得了竞争性编程的启迪。神树是一棵有根树$$$^{\text{*}}$$$,具有$$$n$$$节点,标记为$$$1$$$到$$$n$$$。节点 $$$v$$$ 的神圣性,表示为 $$$d(v)$$$,被定义为从根到节点 $$$v$$$ 的唯一简单路径上的最小节点标签。
Aryan,作为一个饥饿的竞争程序员,要求 Harshith 传授知识。 Harshith 同意了,条件是 Aryan 被赋予两个正整数 $$$n$$$ 和 $$$m$$$,并且他必须构造一棵具有 $$$n$$$ 个节点的神树,使得树的总神性为 $$$m$$$,即 $$$\displaystyle\sum\limits_{i=1}^n d(i)=m$$$。如果不存在这样的树,雅利安必须报告这是不可能的。
由于渴望知识,雅利安向你寻求帮助来完成这项任务。作为他的好朋友,帮助他解决任务。
$$$^{\text{*}}$$$树是没有环的连通图。 有根树是一棵树,其中一个顶点是特殊的,称为根。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le m \le 10^{12}$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。
输出
对于每个测试用例,在一行中输出一个整数 $$$k$$$ — 树的根。
接下来是 $$$n-1$$$ 行,每行包含树的一条边的描述 — 一对正整数 $$$u_i,v_i$$$ ($$$1\le u_i,v_i\le n$$$, $$$u_i\ne v_i$$$),表示第 $$$i$$$ 条边连接顶点$$$u_i$$$ 和 $$$v_i$$$。
边缘和边缘的顶点可以按任意顺序打印。如果有多个解决方案,请打印其中任何一个。
如果没有解决方案,则打印“-1”。
示例
输入复制
21 24 6
输出复制
-1 3 3 1 1 2 2 4
注意
在第一个测试用例中,有一个值为 $$$1$$$ 的节点,因此不可能获得 $$$2$$$ 的总和。
在第二个测试用例中,对于以 $$$3$$$ 为根的给定树,可以得到 $$$6$$$ 的总和。