BPM Infrastructure Damage

Byteotia is known for its minimalist road infrastructure: between any two towns there is exactly one simple (undirected) path. However, a new device called the Bit Polarizing Magnet (BPM) will forcibly orient each road to become one‐way. Depending on how the BPM polarizes each road, the connectivity between towns may change dramatically.

More precisely, given an undirected tree with n nodes (towns) and n-1 edges (roads), each road will be assigned an orientation (one of its two directions). For any two distinct towns u and v, let P(u,v) be the unique simple path between them. The pair {u,v} is considered connected if it is possible to travel from one town to the other following the road directions; that is, if all edges along P(u,v) are oriented in one consistent direction (either all in the direction from u to v or all from v to u).

Your task is to determine two numbers:

1. The minimum number of connected pairs that can be achieved by a suitable assignment of road orientations.
2. The maximum number of connected pairs that can be achieved by a suitable assignment of road orientations.

Note: Here a pair of towns is unordered (i.e. {u,v} is the same as {v,u}). It can be shown that the minimum possible number is always n-1 (since every road connects its two endpoints regardless of its orientation), whereas the maximum depends on the structure of the tree. In fact, one optimal strategy for the maximum is to choose a town r and orient each edge so that the unique simple path from r to any other town is directed away from r. In that case, the number of connected pairs is equal to the sum of the distances from r to all other nodes. By trying all possible choices for r (which can be done efficiently using a re-rooting technique), one may obtain the maximum achievable number of connected pairs.

The problem may also be formulated in a more mathematical way using LaTeX. For example, if we denote by \( S(r) = \sum_{v \in V} d(r,v) \) the sum of distances from a chosen root r to all nodes, then the maximum number of connected pairs is given by \( \max_{r \in V} S(r) \) and the minimum is \( n-1 \).

inputFormat

The first line contains an integer n (the number of towns), where n \ge 2.

Each of the following n-1 lines contains two integers u and v (1-based indices) representing an undirected road between towns u and v.

You may assume that the given roads form a tree.

outputFormat

Output two integers separated by a space: the minimum and the maximum possible numbers of connected pairs of towns after the BPM orients every road.

sample

3
1 2
2 3

2 3