给定一棵有 $n$ 个顶点的树，顶点编号从 $1$ 到 $n$，每条边的长度均为 $1$。设 $S$ 为满足以下条件的集合： $S = \{(A, B, C) : dis(A, B) \le \max\{dis(A, C), dis(B, C)\}, 1 \le A, B, C \le n, A \neq B, A \neq C, B \neq C\}$ 其中 $dis(A, B)$ 表示从顶点 $A$ 到顶点 $B$ 的最短路径长度。求集合 $S$ 的大小。

输入格式

输入包含多组测试数据。对于每组测试数据： 第一行包含一个整数 $n$ ($3 \le n \le 100000$)，表示顶点数。 接下来 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，表示顶点 $u_i$ 和 $v_i$ 之间有一条边。 所有测试数据的 $n$ 之和不超过 $100000$。

输出格式

对于每组测试数据，输出一个整数，表示 $S$ 的大小。

样例

输入格式 1

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

输出格式 1

4
18