给你一棵有 $$$n$$$ 个节点的树。对于每个节点,您可以将其着色为 $$$0$$$ 或 $$$1$$$。
路径 $$$(u,v)$$$ 的值等于 $$$u$$$ 和 $$$v$$$ 之间最短路径的节点颜色的 MEX$$$^\dagger$$$。
着色值等于所有路径 $$$(u,v)$$$ 的值之和,使得 $$$1 \leq u \leq v \leq n$$$。
树的任何颜色的最大可能值是多少?
$$$^{\dagger}$$$ 数组的 MEX(排除最小值)是不属于该数组的最小非负整数。例如:
- $$$[2,2,1]$$$ 的 MEX 是 $$$0$$$,因为 $$$0$$$ 不属于该数组。
- $$$[3,1,0,1]$$$ 的 MEX 是 $$$2$$$,因为 $$$0$$$ 和 $$$1$$$ 属于数组,但 $$$2$$$ 不属于该数组。
- $$$[0,3,1,2]$$$ 的 MEX 是 $$$4$$$,因为 $$$0$$$、$$$1$$$、$$$2$$$ 和 $$$3$$$ 属于该数组,但 $$$4$$$ 不属于该数组。
输入
每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 树中的节点数。
每个测试用例的以下 $$$n-1$$$ 行包含 $$$2$$$ 整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n, a_i \neq b_i$$$) - 表示顶点 $$$a_i$$$ 和 $$$a_i$$$ 之间的边$$$b_i$$$。保证给定的边形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印树的任何颜色的最大可能值。
示例
输入 #1
4 3 1 2 2 3 4 1 2 1 3 1 4 10 1 2 1 3 3 4 3 5 1 6 5 7 2 8 6 9 6 10 1
输出 #1
8 15 96 1
注意
在第一个示例中,我们将为 $$$1$$$ 中的顶点 $$$2$$$ 和 $$$0$$$ 中的顶点 $$$1,3$$$ 着色。之后,我们考虑所有路径:
- $$$(1,1)$$$ 价值 $$$1$$$
- $$$(1,2)$$$ 价值 $$$2$$$
- $$$(1,3)$$$ 价值 $$$2$$$
- $$$(2,2)$$$ 价值 $$$0$$$
- $$$(2,3)$$$ 价值 $$$2$$$
- $$$(3,3)$$$ 价值 $$$1$$$
我们注意到值的总和是 $$$8$$$,这是可能的最大值。