← 返回题目列表

Codeforces · 538/E

E. 造物主再玩一次

中文机器翻译题面 查看原题

Demiurges Shaambambukli 和 Mazukta 喜欢看普通人的比赛。今天,他们注意到两个人正在玩以下游戏。

有一棵有n个节点的有根树,其中m个是叶子(叶子是没有任何子节点的节点),树的边从父节点指向子节点。在树的叶子中,从 1 到 m 的整数的放置方式使得每个数字恰好出现在一个叶子中。

最初,树的根包含一个片段。两个玩家轮流移动该棋子,在移动过程中,玩家将棋子从当前节点移动到其子节点之一;如果玩家不能采取行动,游戏立即结束。游戏的结果是棋子完成移动时放置在叶子上的数字。第一个行动的玩家试图最大化游戏结果,而第二个玩家则相反,试图最小化结果。我们可以假设两名球员的移动都处于最佳状态。

造物主是无所不能的,所以在比赛前他们可以任意重新排列叶子中放置的数字。 Shaambambukli 希望重新排列数字,以便当双方都发挥最佳水平时,游戏的结果尽可能大,而 Mazukta 希望结果尽可能小。如果由Shambambukli 重新排列数字,那么游戏的结果会是什么?如果由Mazukta 重新排列数字,又会是什么结果?当然,造物主会选择最好的数字排列方式。

输入

第一行包含一个整数 n — 树中的节点数 (1 ≤ n ≤ 2·105)。

接下来的 n - 1 行中的每一行都包含两个整数 ui 和 vi (1 ≤ ui, vi ≤ n) - 树边缘的末端;边从节点 ui 通向节点 vi。保证所描述的图是一棵有根树,根为节点1。

输出

打印两个空格分隔的整数——游戏的最大可能结果和最小可能结果。

示例

输入 #1

5
1 2
1 3
2 4
2 5

输出 #1

3 2

输入 #2

6
1 2
1 3
3 4
1 5
5 6

输出 #2

3 3

注意

考虑第一个样本。该树包含三个叶子:3、4 和 5。如果我们将最大数字 3 放在节点 3 处,那么第一个玩家移动到那里,结果将为 3。另一方面,很容易看出,对于任何重新排列,第一个玩家可以保证结果至少为 2。

在第二个示例中,无论排列如何,第一个玩家都可以沿着以编号 3 的叶子结束的路径前进。