Тимур решил заняться пробежками по общежитию. Он мотивирует себя блинами. Общежитие состоит из n комнат, некоторые пары из которых соединены переходами длиной 10 метров. Общежитие является деревом, то есть для каждой пары комнат существует ровно один путь их соединяющий.
Каждая комната содержит тарелку, в которой находится ровно $$$k$$$ блинов. Каждый переход содержит тарелку, в которой находится ровно 2 блина.
Пробежка Тимура выглядит следующим образом:
Тимуру стало интересно, какое максимальное количество метров он сможет пробежать, если выберет стратегию оптимально. Помогите ему определить это.
Первая строка теста содержит одно целое число $$$t$$$ $$$(t \le 100)$$$ — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных, разделенные пустой строкой.
Первая строка набора тестовых данных содержит два целых числа $$$n$$$, $$$k$$$ $$$(1 \le n \le 10^5, 1 \le k \le 10^9)$$$.
Следующая $$$n − 1$$$ строка набора тестовых данных содержит два целых числа $$$v$$$, $$$u$$$ $$$(1 \le v, u \le n, u \neq v)$$$ — описание переходов. Гарантируется, что переходы задают дерево.
Гарантируется, что сумма $$$n$$$ в тестовых наборах не превосходит $$$10^5$$$.
Для каждого набора тестовых данных выведите в отдельной строке одно целое число — ответ на него.
| Группа | Баллы | Доп. ограничения | Комментарий | |
| sum$$$_n$$$ | $$$k$$$ | |||
| $$$0$$$ | 0 | — | — | Тесты из условия |
| $$$1$$$ | 2 | $$$n \le 1$$$ $$$000$$$ | $$$k=1$$$ | |
| $$$2$$$ | 2 | — | $$$k=1$$$ | |
| $$$3$$$ | 3 | $$$n \le 300$$$ | $$$k=2$$$ | |
| $$$4$$$ | 4 | $$$n \le 20$$$ | — | |
| $$$5$$$ | 4 | $$$n \le 1$$$ $$$000$$$ | — | |
| $$$6$$$ | 5 | — | — | |
Тесты к этой задаче состоят из 6 групп. Каждый тест в группе оценивается в 1 балл.
3 7 1 1 2 1 3 2 4 2 5 3 6 3 7 4 2 1 2 1 3 1 4 2 10 1 2
40 40 20
1 12 2 7 8 4 5 7 11 8 10 6 7 4 3 9 7 3 2 4 6 1 2 12 11
160
