题目描述

有一颗树，你需要求出一个排列 $p$ ，使得 $\sum_{(u,v)是一条树上的边}|p_{u}-p_{v}|$ 最小，请输出最小值。

输入格式

第一行输入一个正整数 $T$ ，表示有 $T$ 组数据。 接下来对于每组数据输入两个正整数 $n$ ，接下来 $n-1$ 行，每行输入一条边 $(x,y)$ ，表示树上的一条边。

输出格式

输出 $T$ 行表示答案。

样例输入1

1
5
1 2
1 3
2 4
2 5

样例输出1

5

样例输入2

1
10
1 2
2 3
3 4
3 5
1 6
2 7
2 8
7 9
3 10

样例输出2

14

数据规模和约定

特殊性质$A$：仅有一个节点的度数$>2$。

特殊性质$B$：每个点的儿子个数$≤10$。

对于所有测试点均满足 $T , \sum n≤10^6$。