In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].

If you are familiar with IRC chat, the support team is also reachable on PIRC network (`irc.pirc.pl`

) in `#szkopul`

channel. If you are not, just use email.

Please do not ask us things like "how to solve task XYZ?".

Please remember that the support team has to sleep sometimes or go to work in real life.

<Submit a solution> [0/100]**Task statistics**

Number of users: 91

Number of users with 100 points: 27

Average result: 78.3187

# Polarization

### Memory limit: 128 MB

## Input

## Output

## Example

**Sample grading tests:**

Number of users: 91

Number of users with 100 points: 27

Average result: 78.3187

Everyone knew it would only be a matter of time. So what? Faced for years on, a peril becomes the every-day reality. It loses its meaning...

Today the letter of the Bitotian char Bittard to the Byteotian king Byteasar was released to the public. Bitotia requested annexation of the whole Byteotia on pain of using the Bit Polarizing Magnet (BPM). If used, the BPM would make each and every road in Byteotia unidirectional. The enemy knows only too well that this could be a fatal blow to the minimalist Byteotian infrastructure - there is a unique way between each pair of towns.

How badly can the BPM damage the Byteotian infrastructure? Determine the minimum and the maximum number of such pairs of towns that it will still be possible to travel from one of them to the other while observing the new roads orientation.

The first line of the standard input gives a single integer (), the number of towns in Byteotia. The lines that follow describe these roads. Each such line holds two integers, and (), which indicate that there is a direct road (still bidirectional at the moment) linking the towns no. and .

In tests worth 60% of the total points, the additional constraint holds; moreover, in some of those, worth 30% of the total points, it even holds that .

Two integers should be printed to the first and only line of the standard output. The first number should be the minimum and the second - the maximum number of pairs of towns which could remain connected (though in one direction only) after the roads are polarized.

For the input data:

4 1 2 1 3 1 4

the correct result is:

3 5

For the input data:

8 1 2 2 3 3 4 4 5 5 6 6 7 7 8

the correct result is:

7 28

`1ocen`: , a "comb";`2ocen`: , a complete binary tree;`3ocen`: , two "stars" joined by an edge;`4ocen`: , two "stars" joined by an edge;`5ocen`: , a "star" of maximum size.

*Task author: Jan Kanty Milczek*