# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## Afifa's ITS

Imagine some made up story here including Afifa (my little sister) and an Intelligent Transport System, which ultimately leads to the main problem.

You are given a connected tree containing **N** nodes and **N - 1** bidirectional edges. That means, you can go from one node to any other node. Every node **i** has some weight **w _{i}**. Let’s keep it simple and say that

**w**for the

_{i}= i**i**node. Let this tree be called A.

^{th}Let’s call a node **terminal** if it has one edge attached to it or no edge at all.

You have to pick a “part” of this tree that’s also a tree. You can pick the entire tree as well. Let this new tree be called B.

**fig - 1** denotes an example of tree **A**. **fig - 2** and **fig - 3** shows two of the many possible ways to pick tree **B**. Now, you have to do this in a way so that the cost is maximum.

The cost of choosing tree B = ( minimum weight among the terminals of B ) * ( number of edges in B )

For fig -2, cost is minimum(3, 4, 6) * 3 = 9 and for fig - 3, cost is minimum(1, 6) * 4 = 4. Please note that neither of the costs are maximum.

### Input

The first line contains a single integer **N (1 ≤ N ≤ 100000)** - number of nodes in the tree.
Each of the next **N - 1** lines contains two integers **u** and **v (1 ≤ u, v ≤ N)** - denoting an edge of the tree.

### Output

Print the maximum possible cost of new tree **B**.

### Samples

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

7 2 4 1 2 2 5 3 7 4 7 6 7 | 20 |

**Sample I/O Explanation:**

Here, tree B, marked with bold edges, has two terminals with weight 5 and 6. Number of edges in B equals 4.

So cost is minimum(5, 6) * 4 = 20, which is the maximum possible cost for this case.

#### kfoozminus

→

Login to submit