题目描述

给定一棵 $n$ 个点的树，节点编号为 $1\sim n$，你需要依次做以下操作：

• 选择一条边 $(x,y)\ (x\le y)$，删去这条边。
• 选择 $1\le a\le n$，连接边 $(a,b)$，需要保证连边后仍是一棵树。

$x$ 是树的重心，当且仅当删去 $x$ 及其相关的边后，树分裂成的连通块中，最大的连通块最小。有几种 $(x,y,a,b)$ 的合法选择方法，使得做完这两个操作后树的重心唯一？

输入格式

本题输入量很大，请选手使用读入优化。

第一行一个正整数 $n$。

接下来 $n-1$ 行，每行两个正整数 $x,y$，表示树上有一条边 $(x,y)$。

输出格式

输出一行一个非负整数，$(x,y,a,b)$ 的满足条件的选择方法数。

样例

样例输入 1

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

样例输出 1

83

样例输入 2

2
1 2

样例输出 2

0

样例输入 3

3
1 2
1 3

样例输出 3

4

数据范围

本题捆绑测试。

对于所有数据，$2\le n\le 2\times 10^6$，保证输入合法。详细数据范围如下表：

• 方法 A：对于每个 $2\le i\le n$，独立均匀随机 $\max(i-5,1)\le j\le i-1$，在树上连边 $(i,j)$。得到树的形态后，随机打乱点的编号。