Byteland 的市民们开始按照现代城市规划标准建设一座新城市 Bittown。两位著名的城市规划师 Adilkhan Paradoxny 和 Temirlan Bitihirovich 受聘设计这座新城市的规划。

Bittown 将拥有 $n$ 个十字路口和 $n - 1$ 条连接它们的双向街道。保证从任何一个十字路口出发，沿着 Bittown 的街道都可以到达其他任何一个十字路口。此外，每个十字路口都会建造一栋单户住宅。

根据规划，Bittown 将建造两所学校。然而，规划师们仍然需要选择两个十字路口来建造这些学校。请注意，如果在一个十字路口建造了学校，该十字路口仍然会有一栋住着一户家庭的住宅。也可以在同一个十字路口建造两所学校。

当然，对于规划师来说，让新城市的居民尽可能快地到达学校是很重要的。每个家庭都会开车前往离他们家最近的学校。

让我们将十字路口编号为 $1$ 到 $n$，并令 $d(v, u)$ 为从十字路口 $v$ 到十字路口 $u$ 所需的最少街道数量。假设学校建在编号为 $a$ 和 $b$ 的十字路口。那么，学校的不便程度 $f(a, b)$ 定义为每个家庭到最近学校的距离之和。形式上，$f(a, b) = \sum_{v=1}^{n} \min[d(a, v), d(b, v)]$。

两位规划师都非常自负，不愿意与对方讨论设计方案。因此，他们每个人都将独立选择其中一所学校的未来位置。

考虑 3 种可能的情况：

1. 你负责为两所学校选择十字路口。在这种情况下，找出 $1 \le a, b \le n$ 时最小的不便程度 $f(a, b)$。
2. Temirlan Bitihirovich 想要在十字路口 $a = 1$ 处建造一所学校，而 Adilkhan Paradoxny 向你寻求帮助。找出当 $1 \le b \le n$ 且 $a = 1$ 时最小的不便程度 $f(a, b)$。
3. Adilkhan Paradoxny 向你寻求帮助，但 Temirlan Bitihirovich 没有透露他的计划。在这种情况下，你需要找出对于 $a$ 从 $1$ 到 $n$ 的每个值，当 $1 \le b \le n$ 时最小的不便程度 $f(a, b)$。

编写一个程序，找出上述场景之一中最小的不便程度。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 1000$) —— 测试用例的数量。

接下来是测试用例的描述。

每个测试用例的第一行包含两个数字 $n$ 和 $p$ ($1 \le n \le 10^5, 1 \le p \le 3$) —— Bittown 中的十字路口数量和你所面临的场景编号。

接下来的 $n - 1$ 行包含若干对 $(u_i, v_i)$ ($1 \le u_i, v_i \le n, u_i \neq v_i$，其中 $1 \le i \le n - 1$) —— 由第 $i$ 条道路连接的十字路口编号。

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

输出格式

对于输入中的每个测试用例，请在单独的行中按以下格式打印答案：

• 如果 $p = 1$，打印一个整数 —— $f(a, b)$ 的最小可能值。
• 如果 $p = 2$，打印一个整数 —— 当 $a = 1$ 时 $f(a, b)$ 的最小可能值。
• 如果 $p = 3$，打印 $n$ 个整数 $(e_1, \dots, e_n)$，其中 $e_i$ 是当 $a = i$ 时 $f(a, b)$ 的最小可能值。

子任务

定义 $S$ 为所有测试用例中 $n$ 的总和。

样例

输入 1

3
6 1
1 2
2 3
2 4
4 5
4 6
7 2
1 2
2 3
3 4
3 5
2 6
1 7
7 3
1 2
2 3
3 4
3 5
2 6
1 7

输出 1

4
6
6 6 6 7 7 8 6

说明

在第一个测试用例中 $p = 1$，当 $(a, b) = (2, 4)$ 时达到 $f(a, b)$ 的最小值。在这种情况下，不便程度等于 $1 + 0 + 1 + 0 + 1 + 1 = 4$。

在第二个测试用例中 $p = 2$ 且固定 $a = 1$，当 $b = 3$ 时达到 $f(a, b)$ 的最小值。在这种情况下，不便程度等于 $0 + 1 + 0 + 1 + 1 + 2 + 1 = 6$。