CF2120C.Divine Tree

Harshith 通过在一棵“神圣树”下修炼，获得了竞赛编程的启迪。一棵神圣树是一个有 $n$ 个节点的有根树，节点编号为 $1$ 到 $n$。节点 $v$ 的神圣值 $d(v)$ 被定义为从根到节点 $v$ 的唯一路径上的最小节点编号。

Aryan 作为一名渴望知识的竞赛程序员，请求 Harshith 传授知识。Harshith 同意了，但条件是 Aryan 会得到两个正整数 $n$ 和 $m$，他需要构造一棵有 $n$ 个节点的神圣树，使得整棵树的神圣值之和为 $m$，即 $\displaystyle\sum\limits_{i=1}^n d(i)=m$。如果不存在这样的树，Aryan 必须报告“不可能”。

Aryan 为了获得知识，向你寻求帮助。作为他的好朋友，请你帮助他完成这个任务。

$^{\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”。

在第一个测试用例中，只有一个节点，编号为 $1$，所以无法得到和为 $2$。

在第二个测试用例中，可以以 $3$ 作为根节点构造一棵树，使得神圣值之和为 $6$。

由 ChatGPT 4.1 翻译