Description

每个人都知道这只是时间问题。那么又如何呢？

面对多年的威胁，这种危险成为了日常现实。

它失去了意义……

今天，Bitotia 的 char Bittard 给 Byteotia 国王 Byteasar 的信被公开了。

Bitotia 要求吞并整个 Byteotia，否则将使用 Bit 极化磁铁（BPM）。

如果使用，BPM 将使 Byteotia 的每条道路变为单向。

敌人非常清楚，这可能会对极简的 Byteotia 基础设施造成致命打击——在每对城镇之间只有唯一的路径。

BPM 能对 Byteotia 的基础设施造成多大的破坏？

确定在新的道路方向下，仍然可以从一个城镇到另一个城镇的最小和最大城镇对数。

Input Format

标准输入的第一行给出一个整数 $n$ ($1 \leq n \leq 250\,000$)，表示 Byteotia 中的城镇数量。

接下来的 $n-1$ 行描述这些道路。

每行包含两个整数，$a$ 和 $b$ ($1 \leq a, b \leq n$)，表示目前仍为双向的直接道路连接城镇 $a$ 和 $b$。

在占总分 60% 的测试中，额外的约束 $n \leq 5\,000$ 成立；此外，在其中一些占总分 30% 的测试中，甚至有 $n \leq 1\,000$。

Output Format

标准输出的第一行应打印两个整数。

第一个数字应为在道路极化后仍然可以连接的城镇对数的最小值，第二个数字应为最大值（尽管仅为单向）。

4
1 2
1 3
1 4

3 5

Hint

题面翻译由 ChatGPT-4o 提供。