给定一棵有 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。路径定义为一个不同的顶点序列 $(v_1, \dots, v_k)$，满足 $k \ge 1$，对于所有 $1 \le i \le k-1$，$v_i v_{i+1}$ 是一条边，且 $v_1 \le v_k$。

计算满足以下条件的路径数量：顶点 $v_1, \dots, v_k$ 构成一个连续的整数区间，或者更正式地说，集合 $\{v_1, \dots, v_k\} = \{a, a+1, \dots, b\}$，其中 $a \le b$ 为某些整数。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 50\,000$)。接下来的 $N-1$ 行包含树的边。其中第 $i$ 行包含两个空格分隔的整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le N$)，表示 $u_i v_i$ 是一条边。保证给定的图是一棵树。

输出格式

在一行中输出符合条件的路径数量。

样例

输入 1

3
1 2
1 3

输出 1

5

说明 1

路径为 $(1), (2), (3), (1, 2)$ 和 $(2, 1, 3)$。