旅行

时间限制：2000MS 512MB

题目描述

璃歌要去Z省旅游！

Z省共有 $n$ 个城市，这些城市恰好由 $n - 1$ 条双向通路构成一颗树。

璃歌的旅行路线可以看作一条从起点 $s$ 到终点 $t$ 的简单路径(i.e.，路径的点集 $V$ 和边集 $E$ 中的元素两两不同，称为简单路径)。好不容易出来旅游，璃歌自然希望他的旅行路线是有趣的：璃歌认为一条旅行路线是有趣的当且仅当以起点 $s$ 到终点 $t$ 的路径满足以下性质：

• 该路径是树的一条直径 (i.e.，树的直径是树中最长的简单路径)

璃歌的旅行过程如下：

• 正式出发前，璃歌会提前给Z省的每个城市赋一个权值，这些城市的权值集合构成 $1$ 到 $n$ 的排列。

• 一开始，璃歌会在所有直径的端点中选择某点作为旅行的起点 $s$ ；

• 当璃歌位于城市 $u$ 时：

  • 若与 $u$ 相邻的点中有未走过的点，则 $u \neq t$ ，璃歌会在保证最终的旅行路线有趣的前提下移动至与城市 $u$ 有通路直接相连且权值最大的城市 $v$ （显然这样的城市 $v$ 一定存在）；

  • 否则 $u$ 一定是叶子结点且 $u = t$，璃歌停止在城市间移动并离开Z省。

可以证明在此规则下璃歌的旅行路线最终总是有趣的（总是一条直径）。

另外，璃歌将一条路径的值定义为路径上所有被经过的城市（包括起点 $s$ 和终点 $t$ ）的权值和。璃歌想知道在所有可能的赋值方式和选择合法起点的方案下，璃歌按照上述规则在城市中移动所形成的所有合法路径中，路径的值最小为多少？

输入描述

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。接下来是 $T$ 个测试用例的描述。

对于每个测试用例：

• 第一行包含一个整数 $n$ $(2 \le n \le 1.2 \cdot 10^6)$，表示城市数量。

• 接下来 $n - 1$ 行，每行两个整数 $u$ 和 $v$ $(1 \le u, v \le n, u \neq v)$，表示有一条双向通路连接城市 $u$ 和 $v$。

保证所有测试用例中 $n$ 的总和不超过 $1.2 \cdot 10^6$。

输出描述

对于每个测试用例，输出一行包含一个整数，表示这个最小值。

输入样例

2
3
1 2
2 3
5
1 2
1 3
1 4
1 5

输出样例

6
8

输入样例

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

输出样例

10
11
18