Первая строка содержит целое число $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$.
