题目描述

题目译自 XX Olimpiada Informatyczna — III etap Polaryzacja

每个人都知道，这只是时间问题。但那又如何？当威胁年复一年悬在人类头顶，它便融入了日常，渐渐失去了震慑力……

今日，Bitocja 的统治者 Ziemobit 致信 Bajtocja 国王 Bajtazar 的密函内容公开。Bitocja 要求吞并整个 Bajtocja，并威胁使用「比特极化磁铁」（BMP）。此武器会将 Bajtocja 的每条道路变为单向。敌人深知这将是致命一击，因为 Bajtocja 的基础设施极其精简——任意两座城市间只有唯一一条路径。

在 BMP 作用后，Bajtocia 的路网会变成什么样？请计算在道路单向化后，城市对之间可达的最小和最大数量（即从一座城市可沿单向道路到达另一座城市的不同城市对数）。

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 250000$），表示 Bajtocja 的城市数量。

接下来的 $n-1$ 行描述道路，每行包含两个整数 $u, v$（$1 \leq u < v \leq n$），表示城市 $u$ 和 $v$ 间存在一条（当前仍为双向的）道路。

输出格式

输出一行，包含两个整数，用单个空格分隔，分别表示道路极化后可达城市对的最小和最大数量。

样例 1

输入：

4
1 2
1 3
1 4

输出：

3 5

样例 2

输入：

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

输出：

7 28

附加样例

• $n=10$，梳状图样例。
• $n=15$，完全二叉树。
• $n=100$，两颗星形图通过一条边连接。
• $n=10000$，两颗星形图通过一条边连接。
• $n=250000$，最大规模星形图。

数据范围与提示

对于 30% 的测试数据，$n \leq 100$。

对于 60% 的测试数据，$n \leq 10000$。