Soldering the Amazing Structure

The cows want to build an Amazing Structure – a connected graph with N nodes and N − 1 edges (each of unit length) – by soldering wires together. They may buy a wire of integer length L at a cost of L²; however, they are not allowed to cut wires or solder one endpoint to another. Instead, they may solder the endpoint of one wire onto some interior point (i.e. not an endpoint) along the length of another wire. (Note that several solder junctions may occur at the same point.)

The cows’ plan is given as a tree: each of the N − 1 edges is specified by a pair of integers A and B (with 1 ≤ A, B ≤ N and A ≠ B) so that every two nodes are connected.

The challenge is to choose a partition of the tree’s edges into wire segments (each segment being a contiguous path in the tree) so that by soldering pieces together – always attaching an endpoint to an interior point of some already‐purchased wire – the entire tree is built and the total cost is minimized. The cost of a segment is the square of its length. (Notice that if a segment has length 1 then both of its endpoints are “free” and cannot be used as a soldering site; hence, in any valid covering of a non‐path tree at least one wire must have length at least 2, so that it has an interior point available for soldering.)

A useful reformulation is as follows. Any valid partition of the tree into wires must satisfy:

• The sum of the lengths of all wires is exactly N − 1.
• If a vertex is used to solder (i.e. if two wires meet there) then the solder must be attached along the interior of one of the wires (which therefore must have length at least 2). In other words, at any vertex at most one solder junction may be performed.

One can show that an optimal solution always uses a partition in which one of the wires – the main wire – covers N − k edges (so that its cost is (N − k)²), and every other (soldered) wire covers exactly one edge (each costing 1). Connectivity forces that at least one solder junction is needed (so that if the tree is not a simple path, we must have k ≥ 2) and the allowed number of solder junctions is bounded by the number of vertices having degree at least 2. (Note that in a simple path a single wire is feasible.)

Thus, if we let k be the total number of wires (with 1 wire being the main wire and k − 1 wires of length 1) then the total cost is

subject to the constraints that if the tree is not a path then k ≥ 2, that the main wire has length at least 2 (i.e. N − k ≥ 2), and that we cannot solder wires at more than M vertices, where M is the number of vertices with degree at least 2 (so that k ≤ M + 1).

Your task is to compute the minimum possible cost given the tree. (For trees that are simple paths, a single wire is allowed.)

inputFormat

The first line contains a single integer N (1 ≤ N ≤ 50,000).

Each of the next N − 1 lines contains two integers A and B indicating that there is an edge between nodes A and B. It is guaranteed that these edges form a tree.

outputFormat

Output a single integer – the minimum total cost to build the structure.

sample

4
1 2
2 3
3 4

5