← 返回题目列表

Codeforces · 2120/C

C. 神树

中文机器翻译题面 查看原题

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”。

示例

输入
复制

2
1 2
4 6

输出
复制

-1
3
3 1
1 2
2 4

注意

在第一个测试用例中,有一个值为 $$$1$$$ 的节点,因此不可能获得 $$$2$$$ 的总和。

在第二个测试用例中,对于以 $$$3$$$ 为根的给定树,可以得到 $$$6$$$ 的总和。