G. Graphoria's Villages Visit
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the mythical land of Graphoria, there exists a magical forest composed of $$$N$$$ interconnected trees forming a single grand tree. Each node of the tree represents a village, and each village, $$$u$$$, sends a traveler to every other village, $$$v$$$, with a greater value ($$$v \gt u$$$) exactly once, using the unique paths between them.

The wise king of Graphoria, King Algor, has issued a decree. He wants to know which paths (edges) in the forest are the most traversed by the travelers and how frequently they are used. The kingdom's prosperity depends on understanding these patterns, as it will help in maintaining the paths and ensuring the smooth transit of its inhabitants.

You are given a tree with $$$N$$$ nodes (numbered from $$$1$$$ to $$$N$$$) and $$$N-1$$$ edges. Each node in the tree represents a village.

Your task is to determine:

1. The maximum number of times any single edge in the tree is visited.

2. The number of edges that are visited exactly this number of times.

Input

The first line contains a single integer $$$N$$$ $$$(2 \leq N \leq 10^6)$$$, the number of nodes in the tree.

Each of the next $$$N-1$$$ lines contains two integers $$$U$$$ and $$$V$$$ $$$(1 \leq U, V \leq N)$$$ indicating there is an edge between nodes $$$U$$$ and $$$V$$$.

Output

Print two integers. The first integer is the maximum number of times any single edge is visited. The second integer is the number of edges that are visited exactly this number of times.

Examples
Input
7
1 2
1 3
2 4
2 5
3 6
3 7
Output
12 2
Input
5
1 2
2 3
3 4
4 5
Output
6 2