Mansur 是 ACMstan 国的统治者。该国有 $N$ 座城市和 $N-1$ 条双向道路。已知从任意城市出发，都可以通过现有的道路到达其他任何城市。更正式地说，该国是一个树状结构，其中顶点是城市，边是双向道路。

此外，在该国中，恰好连接有一条道路的城市被称为“终端”（terminal）。“路线”（route）是指从一个终端到另一个终端的简单路径。两座城市之间的距离是它们之间路径上的最小道路数。从城市到路线的距离是该城市到路线中任意城市路径上的最小道路数。Mansur 决定在 ACMstan 中实施恰好一条路线，但他只对“困难路线”（hard route）感兴趣。路线的“硬度”（hardness）计算如下：设 $A$ 和 $B$ 是该路线的两个终端，$H$ 是全国任意城市到该路线的最大距离，则该路线的硬度为 $H$ 与 $A$ 和 $B$ 之间距离的乘积。

Mansur 请 Temirulan 找出所有路线中的最大硬度，实际上他想知道有多少条这样的路线。Temirulan 向你寻求帮助。

强烈建议阅读下方的说明。

输入格式

输入的第一行包含一个正整数 $N$ ($2 \le N \le 500000$)，表示该国的城市数量。城市编号从 $1$ 到 $N$。接下来的 $N-1$ 行包含两个正整数，由空格分隔，$u_i, v_i$ ($1 \le u_i, v_i \le N; u_i \neq v_i$)，表示连接城市 $u_i$ 和 $v_i$ 的道路。保证给定的图是一棵树。

输出格式

在一行中输出两个整数，即最大硬度和此类路线的数量，中间用空格分隔。注意，从 $A$ 到 $B$ 的路线和从 $B$ 到 $A$ 的路线是同一条路线。

子任务

本题包含三个子任务：

1. $2 \le N \le 100$。分值 19 分。
2. $2 \le N \le 5000$。分值 33 分。
3. $2 \le N \le 500000$。分值 48 分。

仅当解决方案成功通过所有前置子任务时，才会对当前子任务进行评分。

样例

样例输入 1

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

样例输出 1

6 2

样例输入 2

4
1 2
2 3
2 4

样例输出 2

2 3

样例输入 3

5
1 2
2 3
3 4
4 5

样例输出 3

0 1

说明

简单路径是指没有重复顶点的路径。注意，可能存在不是路线的简单路径。

第一个样例测试： 有四个终端城市，编号为 4、5、6 和 7。对于路线 4-2-1-3-6，距离为 4，其他城市到该路线的距离为 $[1, 1]$，其中最大值为 1，因此该路线的硬度等于 $4 \times 1 = 4$。对于路线 4-2-5，距离为 2，其他城市到该路线的最大距离为 3（来自 6 或 7），路线的硬度等于 $3 \times 2 = 6$。6-3-7 的硬度也为 6，但其他路线的硬度较小。

在第三个样例测试中，只有两个终端城市 1 和 5，因此只有一条路线 1-2-3-4-5，距离为 4，所有城市到路线的最大距离为 0，因为所有城市都已经在这条路线上。硬度等于 $4 \times 0 = 0$。