Пауки — старые враги Ам Няма. Они не меньше его любят есть леденцы, и поэтому они постоянно пытаются не дать монстрику добраться до любимой сладости. Они придумали коварный план, чтобы заманить Ам Няма в ловушку.
Рассмотрим верёвочную конструкцию из n узелков и n - 1 тросика, соединяющего эти узелки. Конструкция образует единое целое, таким образом, тросы с узелками представляют собой дерево. Каждый тросик образованной конструкции имеет свою длину. К узелку x конструкции привязан леденец, который хочет съесть Ам Ням.
Ему стараются в этом помешать y пауков. Они решили опутать леденец и некоторую часть конструкции паутиной, приклеив его таким образом к как можно большей части верёвочного сооружения.
Каждый паук может покрыть паутиной все тросики на пути между двумя произвольными узелками a и b. Таким образом, y пауков могут покрыть множество тросиков, которое является объединением y путей в данном дереве, причём эти y путей могут произвольным образом пересекаться друг с другом. Пауки хотят, чтобы:
- узелок, содержащий леденец, был смежен хотя бы одному тросику, покрытому паутиной
- покрытые паутиной тросики образовывали связную конструкцию (зачем покрывать паутиной части, не связанные с леденцом?)
- суммарная длина тросов, покрытых паутиной, была как можно больше
Пауки ещё не решили, к какому узелку конструкции будет привязан леденец, и сколько пауков будет покрывать конструкцию паутиной, поэтому они обратились к вам за помощью. Помогите им посчитать оптимальный план для нескольких значений x и y.
Выходные данные
На каждый вопрос пауков выведите в отдельной строке одно целое число Ansi — суммарную длину тросов, опутанных паутиной в оптимальном плане.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 3
1 2 2
2 3 2
3 4 2
4 6 1
3 5 10
3 1
2 5
1 1
|
14
13
17
|