В компьютерной игре Dota 2 есть герой Arc Warden. Его ультимейт создает своего клона, который обладает всеми способностями героя. Карта представляет собой дерево из $$$n$$$ вершин с нейтральным крипом в каждой вершине. Напомним, что деревом называется связный неориентированный граф без циклов. Зафармив крипов, герой может получить опыт и золото.
Arc Warden хочет посетить все вершины и зафармить всех крипов. Для этого он выбирает начальную вершину, встаёт в неё и создает своего клона в той же вершине. Затем они с клоном независимо обходят дерево, переходя в соседние по ребру вершины. Разрешается посещать одну вершину более одного раза.
Определите минимальное суммарное расстояние, которое Arc Warden и его клон должны пройти по дереву, чтобы посетить каждую вершину. Расстояние считается как количество рёбер.
Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 500$$$) — количество наборов входных данных.
Первая строка теста содержит целое число $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — количество вершин в дереве.
Следующие $$$n-1$$$ строк описывают рёбра дерева, где каждое ребро соединяет пару вершин $$$u$$$ и $$$v$$$ ($$$1 \leq u,v \leq n$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — минимальное суммарное расстояние, которое должны пройти Arc Warden и его клон, чтобы обойти всё дерево.
351 22 34 25 486 15 88 36 77 52 14 722 1
5 8 1
В первом наборе входных данных выгодно начать в вершине $$$2$$$. Arc Warden может пройти путь $$$2 \to 3 \to 2 \to 1$$$, а его клон может пройти путь $$$2 \to 4 \to 5$$$. Таким образом, суммарно будет пройдено $$$5$$$ рёбер. Можно показать, что ответ лучше получить нельзя.
