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.

Constraints

  • 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?

Sponsors Gold