#CF2120C. 神圣之树
神圣之树
C. 神圣之树
每个测试点时间限制:2 秒
每个测试点内存限制:256 兆字节
Harshith 在一棵神圣之树下训练,从而在竞赛编程中达到了开悟境界。
神圣之树是一棵有根树∗,包含 个节点,节点编号为 到 。
节点 的“神圣度”记为 ,定义为从根节点到节点 的唯一简单路径上,节点编号的最小值。
Aryan 作为一个饥饿的竞赛编程选手,请求 Harshith 传授知识。
Harshith 同意,条件是:Aryan 会得到两个正整数 和 ,并且他必须构造一棵有 个节点的神圣之树,使得该树的总神圣度为 ,即:
如果不存在这样的树,Aryan 必须报告不可能。
为了获取知识,Aryan 向你求助完成这个任务。作为他的好朋友,请帮助他解决这个任务。
∗
树是一个无环连通图。有根树是指树中有一个特殊的顶点称为根。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 ()。
接下来是每个测试用例的描述。
每个测试用例的第一行包含两个整数 和 (,)。
保证所有测试用例的 之和不超过 。
输出
对于每个测试用例,首先输出一行一个整数 —— 树的根节点编号。
然后输出 行,每行描述树的一条边 —— 两个整数 (,),表示第 条边连接节点 和 。
边和顶点可以按任意顺序输出。如果有多个解,输出任意一个。
如果没有解,则输出一行 -1。
示例
输入:
2
1 2
4 6
输出:
-1
3
3 1
1 2
2 4
注意
在第一个测试用例中,只有一个节点,它的值为 ,因此总和不可能为 。
在第二个测试用例中,以 为根的树可以达到总和 ,构造如输出所示。