You are given a tree ** T** with

**nodes, indexed from**

`N`**to**

`1`**. Your task is to find the maximum possible number of edges of an undirected graph**

`N`**containing the same number of nodes as**

`G`**, such that**

`T`**is a minimum spanning tree of**

`T`**.**

`G` The cost of an edge from node ** x** to node

**in**

`y`**is computed as the sum of node indices**

`G`**.**

`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

**. Concretely, each line contains two integers,**

`T`**and**

`x`**denoting that there is an**

`y`**undirected edge**between

**and**

`x`**in**

`y`

`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

**is**

`G`**.**

`T`### Constraints

`1 ≤ N ≤ 10`^{5}

### Sample

Input | Output | Explanation |
---|---|---|

31 2 2 3 | 2 | The only edge we could add is 1 - 3. If we were to add this edge in , the minimum spanning tree of G would be G{(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 is G. 2 |