Пауки — старые враги Ам Няма. Они не меньше его любят есть леденцы, и поэтому они постоянно пытаются не дать монстрику добраться до любимой сладости. Они придумали коварный план, чтобы заманить Ам Няма в ловушку.

Рассмотрим верёвочную конструкцию из n узелков и n - 1 тросика, соединяющего эти узелки. Конструкция образует единое целое, таким образом, тросы с узелками представляют собой дерево. Каждый тросик образованной конструкции имеет свою длину. К узелку x конструкции привязан леденец, который хочет съесть Ам Ням.

Ему стараются в этом помешать y пауков. Они решили опутать леденец и некоторую часть конструкции паутиной, приклеив его таким образом к как можно большей части верёвочного сооружения.

Каждый паук может покрыть паутиной все тросики на пути между двумя произвольными узелками a и b. Таким образом, y пауков могут покрыть множество тросиков, которое является объединением y путей в данном дереве, причём эти y путей могут произвольным образом пересекаться друг с другом. Пауки хотят, чтобы:

• узелок, содержащий леденец, был смежен хотя бы одному тросику, покрытому паутиной
• покрытые паутиной тросики образовывали связную конструкцию (зачем покрывать паутиной части, не связанные с леденцом?)
• суммарная длина тросов, покрытых паутиной, была как можно больше

Пауки ещё не решили, к какому узелку конструкции будет привязан леденец, и сколько пауков будет покрывать конструкцию паутиной, поэтому они обратились к вам за помощью. Помогите им посчитать оптимальный план для нескольких значений x и y.