Polarization

Time limit3sMemory limit512 MB

Summary

Orient every edge of the given tree and report the smallest and largest possible numbers of town pairs connected by a directed path.

Level: Hard8 of 10
Topics: Tree, Dynamic programming, Greedy
Solved: No attempts yet

Problem

Everyone knew this day would come. A danger you live beside for years turns into ordinary life and stops carrying any weight.

Today the letter that Bittard, ruler of Bitotia, sent to Byteasar, king of Byteotia, was made public. Bitotia demands the annexation of all of Byteotia and threatens to use the Bit Polarizing Magnet (BPM) if the demand is refused.

Once the BPM fires, every road in Byteotia becomes one way. Byteotia built its road network as sparsely as it could, so exactly one route runs between any two towns. That is why the blow could be fatal.

Work out how much damage the BPM can do. After every road has been given a direction, count the pairs of towns for which it is still possible to travel from one town of the pair to the other while respecting the new directions. Over all the ways of directing the roads, find the minimum and the maximum of that count.

Input

The first line of input holds one integer $n$ ( $1 \le n \le 250\,000$ ), the number of towns in Byteotia. The towns are numbered from $1$ to $n$ .

Each of the next $n-1$ lines holds two integers $u$ and $v$ ( $1 \le u \le v \le n$ ), meaning that a road directly joins town $u$ and town $v$ . That road is still two way for now. The roads connect the towns so that exactly one route runs between any two of them.

Output

Print two integers on one line, separated by a space: first the minimum, then the maximum number of pairs of towns that stay reachable in one direction after the roads are polarized.

Examples2

Example 1
Input
```
4
1 2
1 3
1 4
```
Expected output
```
3 5
```
Example 2
Input
```
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
```
Expected output
```
7 28
```