小企鹅波罗有一棵树——一个无向连通的无环图,包含n个节点和n-1条边。我们将考虑用 1 到 n 的整数编号的树节点。
今天 Polo 想知道如何找到没有公共节点的路径对的数量。更正式地说,他应该找到由四个整数 a、b、c 和 d 组成的组的数量,使得:
- 1 ≤ a < b ≤ n;
- 1 ≤ c < d ≤ n;
- 没有这样的节点既位于从节点 a 到节点 b 的最短路径上,又位于从节点 c 到节点 d 的最短路径上。
两个节点之间的最短路径是边数最短的路径。
帮助Polo解决这个问题。
输入
第一行包含整数 n (1 ≤ n ≤ 80000) — 树节点的数量。以下 n - 1 行中的每一行都包含一对整数 ui 和 vi (1 ≤ ui, vi ≤ n; ui ≠ vi) — 树的第 i 条边。
保证给定的图是一棵树。
输出
在一行中打印一个整数——问题的答案。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位数字。建议使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
4 1 2 2 3 3 4
输出 #1
2