Village House Swap

There is a village with \(N\) houses and \(N-1\) roads connecting them such that the houses form a tree. Each road has a length of 1. Initially, the \(i\)th villager lives in house \(i\) (houses are numbered from 1 to \(N\)). One day, the villagers decide to swap houses, with the constraint that no villager may remain in his original house (i.e. the relocation permutation is a derangement).

The task is to determine two values:

• The minimum total distance travelled by all villagers and
• The maximum total distance travelled by all villagers,

under some valid derangement of assignments.

Note: For a valid assignment, the total distance is calculated as \(\sum_{i=1}^{N}d(i,\pi(i))\), where \(d(u,v)\) is the length of the unique path between nodes \(u\) and \(v\) in the tree, and \(\pi\) is a derangement (i.e. \(\pi(i) \neq i\) for all \(i\)).

Observations and Hints:

• Any move must have a distance of at least 1. In some cases if it were possible to pair two villagers in adjacent houses, each of them could move along one road (costing 1 each) — however, the structure of the tree may prevent a perfect pairing.
• A key insight is to compute a maximum matching on the tree with the restriction that the two houses in a pair are directly connected (i.e. adjacent). Suppose the maximum matching has \(M\) edges. Then a derangement achieving near-minimum movement can be found with a total distance of
  
  \( \text{min_sum} = 2\times (N - M) \).
  
  (Notice that if two houses are paired, each travels one road; extra cost may be needed when a perfect matching is impossible.)
• For the maximum total distance, one may prove that for every edge \(e\) whose removal splits the tree into two components of sizes \(s\) and \(N-s\), the edge can contribute at most \(2\times \min(s,N-s)\) (each crossing adds 1 to the distance for both directions) and there is an assignment achieving this sum. Therefore,
  
  \( \text{max_sum} = \sum_{e \in \text{tree}} 2\times \min(s_e, N-s_e) \).

Input and Output formats are described below.

inputFormat

The first line contains an integer \(N\) (the number of houses). The following \(N-1\) lines each contain two integers \(u\) and \(v\), indicating there is a road connecting house \(u\) and house \(v\). It is guaranteed that the given graph is a tree.

outputFormat

Output two integers separated by a space: the minimum total distance and the maximum total distance over all valid derangements.

sample

2
1 2

2 2