这是一道交互题，仅支持 C++ 语言提交。

小青鱼计划越过高高的龙门，成为大青龙。但是仅凭小青鱼的力量是越不过龙门的。所以它在被称作老龙宫的溶洞中探险，如果能游历幽深之处，就能获得神奇的云崖潮生之珠。

龙门水道的地下有复杂的溶洞，具体来说，溶洞可以被视为有 $n$ 个节点的树，点的编号为依次为 $1$ 到 $n$。

令 $\mathrm{dist}(u, v)$ 表示树上 $u$ 到 $v$ 的简单路径包含的边数，$f(l, r) = \max\limits_{l \le u \le v \le r} \mathrm{dist}(u, v)$。

小青鱼还不知道溶洞的具体结构。在探险之前，小青鱼打算用探测器对溶洞进行调查。只要在节点 $u,v$ 埋下探测器，就可以算出 $u,v$ 之间的距离 $\mathrm{dist}(u, v)$。

小青鱼需要知道这个溶洞是否具有足够的仙力，只有足够幽曲蜿蜒的地方才能诞生出强大的云崖潮生之珠。

具体地，小青鱼想求出 $\sum_{l=1}^n \sum_{r = l+1}^n f(l, r)$，即区间直径长度之和。这个值同时也是云崖潮生之珠的仙力估计值。

题目保证树的形态是预先给定的，不会根据你的操作而动态生成。

一句话题意：每次可询问 $\mathrm{dist}(u, v)$，需要求出 $\sum_{l=1}^n \sum_{r = l+1}^n f(l, r)$。

实现细节

你需要引用头文件 #include "tree.h"。你可以调用以下函数与交互库进行交互：

int query(int u, int v);

• 这个函数会返回 $u$ 到 $v$ 的距离。
• 你需要保证 $1 \le u, v \le n$。

你不需要，也不应该实现主函数。在本题中，你只需要实现如下函数：

long long solve(int type, int n);

• 其中 $\text{type}$ 表示数据类型，$n$ 表示树的点数，函数的返回值应为 $\sum_{l=1}^n \sum_{r = l+1}^n f(l, r)$。
• 最终测试时，对于每个测试点，交互库会调用恰好 $T$ 次 solve 函数，并根据调用 solve 函数的返回值正误来评分。

在选手目录（题目附件）中，我们提供了 sample.cpp 供你参考，你可以在此基础上实现你的程序。

测试程序方式

本题目录下提供了 grader.cpp 文件（该文件使用了部分标准中不包含的函数，如有需要，可以使用 grader2.cpp）。最终测试的交互库与下发交互库有不同，因此你的实现不应依赖交互库实现。

你需要将你的程序 tree.cpp 和 grader.cpp、tree.h 放置在同一目录下，并在该目录下使用如下编译命令得到可执行程序 tree(.exe)：

g++ -o tree tree.cpp grader.cpp -O2 -std=c++17

可执行程序从标准输入读入以下格式的数据：

• 第一行包含一个正整数 $T$，表示数据组数。

对于每组数据：

• 第一行，共两个整数 $\text{type},n$。交互库保证可以处理 $2 \le n \le 10^5$ 的情况，对于 $n > 10^5$ 的情况不做正确运行保证。
• 接下来 $n - 1$ 行，每行包含两个正整数 $u, v$，表示了树上一条边。你需要保证 $1 \le u, v \le n$ 且输入给出了合法的树的结构。

在本地测试时，请务必保证你的输入格式符合要求，否则我们不保证交互库会正常运行。

如果你的输入合法且没有运行错误，下发的交互库将会根据你的调用输出如下信息：

• 如果某次 query 函数的调用违反了 $1 \le u, v \le n$ 的限制，输出错误信息：Wrong Answer 0!，并且交互库立即终止。
• 如果 solve 函数的返回值正确，那么交互库会输出三个数，依次表示：solve 函数的返回值，$n$ 的值，query 函数的调用次数。

你的程序不应该操作标准输入输出，否则视为攻击交互库。

样例一

见下发文件中的 ex_tree1.in/out。

样例二

见下发文件中的 ex_tree2.in/out。

样例三

见下发文件中的 ex_tree3.in/out。

子任务

对于所有数据，$1 \leq T \leq 10^4, 1 \leq n \leq 10^5, \sum n \leq 3 \times 10^5, lim \geq 8 \times n$。

令 $k=\dfrac{lim}{n}$。

$\text{type}=3$ 的数据保证树为一条链。

$\text{type}=4$ 的数据保证 $f(1,n)\le 8$。

评分方式

本题首先会受到和传统题相同的限制。例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。你只能访问自己定义的和交互库给出的变量及其对应的内存空间，尝试访问其他空间将可能导致编译错误或运行错误。

在以上条件下，若 solve 函数的返回值正确，且在 $T$ 次 solve 过程中调用 query 函数的次数均不超过 $lim$，则相应测试点得满分，否则得 $0$ 分。

在实际测评中，对于子任务 2, 5 我们仅会测试一轮，并根据选手的询问次数给出相对应的分数。

保证在下发的交互库和最终评测的交互库中，query 函数的单次最坏复杂度为 $O(1)$，在题目限制下占用不超过 $1\texttt{s},256\texttt{MB}$。

提示

我们再次提醒：树的形态是预先给定的，不会根据你的操作而动态生成。

你需要注意你的程序的时间开销和空间开销。

通过访问输入输出文件、攻击评测系统或攻击评测库等方式得分属于作弊行为，所得分数无效。

时间限制：$5\texttt{s}$

空间限制：$1\texttt{GB}$