Acmar 和 Ibmar 正在交战！在这个微妙的时期，你负责管理一个在 Acmar 大州内运输重要物资的铁路网络。铁路系统由一系列在各个枢纽点汇合的铁路线组成。虽然在一个枢纽点汇合的铁路线数量没有限制，但该网络的设置使得任意两个枢纽点之间只有一条路径。你曾试图争取在系统中增加一些冗余，即增加额外的铁路线，以便在某些枢纽点之间有两条或多条路径，但现在是战时，预算紧张。

然而，这种情况可能很快就会改变，因为你刚刚从在 Ibmar 工作的双重间谍那里得到了一个可怕的消息：下个月内，敌方间谍计划炸毁其中一个枢纽点！不幸的是，具体的枢纽点尚不清楚，但你很了解你的敌人，你确信他们一定会打击那个“关键枢纽”，即移除该枢纽后，系统中剩余的其他枢纽点之间断开连接的对数最多的那个枢纽点。你没有太多时间采取行动，所以你所能做的就是增加一条连接两个当前未连接枢纽点的新线路，从而减少关键枢纽被摧毁后断开连接的对数。你的任务是确定如何通过增加一条最佳铁路线，使断开连接的对数尽可能小。

输入格式

输入的第一行包含一个整数 $n$ ($2 \le n \le 10\,000$)，表示系统中的铁路线数量。接下来有 $n$ 行，每行包含 $i_1$ 和 $i_2$，表示一条铁路线连接枢纽 $i_1$ 和 $i_2$。枢纽从 0 开始连续编号。所有铁路线都是双向的，且输入中不会出现重复的铁路线。输入中给出的任意两个枢纽点之间恰好有一条路径。

输出格式

输出两个值 $n_1$ 和 $n_2$，其中 $n_1$ 是当敌人摧毁关键枢纽时会断开连接的枢纽对数，$n_2$ 是在你增加最佳铁路线后仍然断开连接的枢纽对数。关键枢纽永远不会多于一个。

样例

样例输入 1

6
0 1
1 2
2 3
2 4
4 5
4 6

样例输出 1

11 5

样例输入 2

2
2 1
0 1

样例输出 2

1 0