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 的叶子结束的路径前进。