Xiao Q has recently learned some graph theory. According to the textbook, the definitions are as follows:

Tree: An undirected graph that is connected and contains no cycles. Each edge has a positive integer weight representing its length. It can be proven that a tree with $N$ nodes has exactly $N-1$ edges.

Path: In a tree, there is at most one simple path between any two nodes. We use $dis(a, b)$ to denote the sum of the lengths of the edges on the path between node $a$ and node $b$. $dis(a, b)$ is called the distance between nodes $a$ and $b$.

Diameter: The longest path in a tree is the diameter of the tree. The diameter of a tree is not necessarily unique.

Now, Xiao Q wants to know the length of the diameter for a given tree, and how many edges are traversed by all diameters of the tree.

Input

The first line contains an integer $N$, representing the number of nodes.

The next $N-1$ lines each contain three integers $a, b, c$, representing an undirected edge between node $a$ and node $b$ with length $c$.

Output

Two lines. The first line contains an integer representing the length of the diameter. The second line contains an integer representing the number of edges that are traversed by all diameters.

Constraints

• For 20% of the test data: $N \le 100$
• For 40% of the test data: $N \le 1000$
• For 70% of the test data: $N \le 100000$
• For 100% of the test data: $2 \le N \le 200000$, all node labels are in the range $1..N$, and edge weights are $\le 10^9$.

For each test case, if the first line of the output file matches the standard output, you receive 20% of the points for that test case. If the second line of the output file matches the standard output, you receive 80% of the points for that test case. These two parts are cumulative.

This problem uses a custom checker. To prevent errors in the custom checker, even if you cannot correctly determine the answer to one of the questions, you should still output a number in the corresponding position.

Examples

Input 1

6
3 1 1000
1 4 10
4 2 100
4 5 50
4 6 100

Output 1

1110
2

Note

There are two diameters in total: the path from 3 to 2 and the path from 3 to 6. Both of these diameters pass through edge $(3, 1)$ and edge $(1, 4)$.