L. Cool Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a tree $$$T$$$ with $$$n$$$ vertices, color each edge of the tree either white or black. A path in the tree is defined as a sequence of vertices $$$v_1, v_2, \ldots, v_k$$$ such that there exists a sequence of edges connecting each consecutive pair of vertices $$$(v_i, v_{i+1})$$$ for $$$1 \leq i \lt k$$$.

A path is considered to be cool if no two edges that share an endpoint also share the same color. Additionally, a path of one vertex, and hence no edges, is also considered a cool path. Find the maximum possible number of cool paths over all possible colorings of the edges.

Input

The first line consists of an integer $$$n\ (1\le n\leq 4\cdot 10^6)$$$, the number of vertices in the tree.

The next $$$n-1$$$ lines contain two integers $$$s_i,t_i\ (1\leq s_i\ne t_i\leq n)$$$, denoting the $$$i$$$-th edge in the tree.

It is guaranteed that the given edges form a tree.

–

Tests in subtasks are numbered from $$$1−25$$$ with samples skipped. Each test is worth $$$\frac{100}{25}=4$$$ points.

Tests $$$1-2$$$ satisfy $$$n \leq 100$$$.

Tests $$$3-7$$$ satisfy $$$n \leq 1000$$$.

Tests $$$8-12$$$ satisfy $$$n \leq 2\cdot 10^4$$$.

Tests $$$13-15$$$ satisfy $$$n \leq 10^5$$$.

Tests $$$16-22$$$ satisfy $$$n \leq 10^6$$$.

Tests $$$23-25$$$ satisfy no additional constraints.

Output

Output an integer, the maximum possible number of cool paths over all possible colorings of the edges.

Examples
Input
3
1 3
2 1
Output
6
Input
5
1 3
4 2
3 5
3 2
Output
14
Note

For the first sample test case, color edge $$$1-3$$$ white and edge $$$2-1$$$ black. Then the paths $$$1,2,3,1-2,1-3,2-1-3$$$ are all cool.

For the second sample test case, color edges $$$1-3,3-5,4-2$$$ black and $$$3-2$$$ white. Then the paths $$$1,2,3,4,5,1-3,2-3,2-4,3-5,1-3-2,2-3-5,3-2-4,1-3-2-4,4-2-3-5$$$.

—

Problem Idea: culver0412

Problem Preparation: culver0412

Occurrences: Advanced L