Харшит достиг просветления в спортивном программировании, тренируясь под Божественным деревом. Божественное дерево — это корневое дерево$$$^{\text{∗}}$$$ с $$$n$$$ вершинами, пронумерованными от $$$1$$$ до $$$n$$$. Божественность вершины $$$v$$$, обозначаемая $$$d(v)$$$, определяется как наименьший номер вершины на единственном простом пути от корня до вершины $$$v$$$.
Ариан, будучи голодным спортивным программистом, попросил Харшита передать ему знания. Харшит согласился при условии, что Ариану будут даны два положительных числа $$$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$$$ невозможно.
Во втором наборе входных данных получить сумму $$$6$$$ возможно с деревом, корнем которого является вершина $$$3$$$.
