 # MonSTer

You are given a tree T with N nodes, indexed from 1 to N. Your task is to find the maximum possible number of edges of an undirected graph G containing the same number of nodes as T, such that T is a minimum spanning tree of G.

The cost of an edge from node x to node y in G is computed as the sum of node indices x + y.

A minimum spanning tree of an undirected graph is defined as a subset of the graph's edges that connects all the vertices together, without any cycles and with the minimum possible total cost of edges.

### Input

The first line of the input contains a single number N.

The following N - 1 lines contains the edges of T. Concretely, each line contains two integers, x and y denoting that there is an undirected edge between x and y in T

### Output

A single number: the maximum number of edges of an undirected graph G with the property that one of the minimum spanning tree of G is T.

• 1 ≤ N ≤ 105

### Sample

InputOutputExplanation
3
1 2
2 3
2The only edge we could add is 1 - 3. If we were to add this edge in G, the minimum spanning tree of G would be {(1, 2), (1, 3)} - cost 7. Since we want it to be {(1, 2), (2, 3)} - cost 8, the maximum number of edges we can have in G is 2.
Questions?