Duck Contest

Duck Friendship

Program time limit: 1 second

Program memory limit: 256 MB

This year, the Community of Pond Members (CPM) has welcomed many new ducks. The community can be represented as an undirected connected tree with $N$ vertices, where each vertex is a duck and each edge is a mentor-apprentice connection.

A duck is considered new if it has exactly one connection. In graph terms, the new ducks are the leaves of the tree.

For any pair of new ducks, consider the simple path between them. Let:

  • $D$ be the length of this path, measured in edges.
  • $F$ be the maximum distance from any vertex in the tree to this path.

The familiarity value of the pair is $D \times F$.

Keane wants to find the maximum familiarity value over all pairs of new ducks, and the number of pairs that achieve this maximum value.

Input

  • The first line contains an integer $N$ — the number of ducks.
  • The next $N - 1$ lines each contain two integers $A_i$ and $B_i$, denoting an edge between ducks $A_i$ and $B_i$.

You should read from standard input.

Constraints

  • $2 \le N \le 10^5$
  • $1 \le A_i, B_i \le N$
  • $A_i \ne B_i$
  • The given graph is an undirected connected tree.

Additionally:

  • For Subtask $1$ ($10\%$ of points): $2 \le N \le 100$.
  • For Subtask $2$ ($10\%$ of points): $2 \le N \le 1000$.
  • For Subtask $3$ ($20\%$ of points): $2 \le N \le 10\,000$.
  • For Subtask $4$ ($60\%$ of points): there are no additional constraints.

Output

  • Print two integers: the maximum familiarity value and the number of unordered pairs of new ducks that achieve this value.

You should write to standard output.

Sample Input

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

Sample Output

6 6

Explanation

If we pick the pair $(5, 8)$, the path is $5 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 8$. Its length is $4$. Every other duck has distance at most $1$ from this path, so the familiarity value is $4 \times 1 = 4$.

If we pick the pair $(4, 8)$, the path is $4 \rightarrow 1 \rightarrow 3 \rightarrow 8$. Its length is $3$. Every other duck has distance at most $2$ from this path, so the familiarity value is $3 \times 2 = 6$.

If we pick the pair $(5, 6)$, the path is $5 \rightarrow 2 \rightarrow 6$. Its length is $2$. Every other duck has distance at most $3$ from this path, so the familiarity value is $2 \times 3 = 6$.

Among all pairs of new ducks in the sample, six pairs have familiarity value $6$, which is the maximum possible value.

Scoring

Your program will be tested on the sample case and several hidden cases. If it produces the correct output for all test cases, it will be considered correct. Recall that your final score for this problem is the score of your highest-scoring submission.

Submit

The contest ended at 8:16 p.m. AEST on Thursday 2nd July. All submissions will be unofficial .