You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

小马非常喜欢爬山，有一天小马来到一座山前，山上有n个亭子，每个亭子都有一个编号，亭子的编号为 1 到 n ，每个编号代表该亭子的海拔高度。

现在小马要在这座山上找到一些路径，从起点到终点需要满足海拔先单调上升后单调下降的性质，起点或终点不同即为不同的路径，问满足条件的路径有多少条，乐于助人的你可以帮助小马解决这个问题吗？

输入格式

第一行输入一个整数 $n(1≤n≤300000)$ 接下来 n−1 行，每行有两个整数，表示这两个亭子直接有一条路

输出格式

输出路径的个数。

输入样例

5
1 5
4 5
2 4
3 4

输出样例

8

数据范围

对于 10% 的数据， 1≤n≤8

对于 50% 的数据， 1≤n≤1024

对于 100% 的数据， 1≤n≤300000

样例解释

符合条件的路径有

1−5−4

1−5−4−3

1−5−4−2

3−4−2

另外四条路径反过来即可，一共八条路径。