CF538E.Demiurges Play Again

Demiurges Shambambukli and Mazukta love to watch the games of ordinary people. Today, they noticed two men who play the following game.

There is a rooted tree on n nodes, m of which are leaves (a leaf is a nodes that does not have any children), edges of the tree are directed from parent to children. In the leaves of the tree integers from 1 to m are placed in such a way that each number appears exactly in one leaf.

Initially, the root of the tree contains a piece. Two players move this piece in turns, during a move a player moves the piece from its current nodes to one of its children; if the player can not make a move, the game ends immediately. The result of the game is the number placed in the leaf where a piece has completed its movement. The player who makes the first move tries to maximize the result of the game and the second player, on the contrary, tries to minimize the result. We can assume that both players move optimally well.

Demiurges are omnipotent, so before the game they can arbitrarily rearrange the numbers placed in the leaves. Shambambukli wants to rearrange numbers so that the result of the game when both players play optimally well is as large as possible, and Mazukta wants the result to be as small as possible. What will be the outcome of the game, if the numbers are rearranged by Shambambukli, and what will it be if the numbers are rearranged by Mazukta? Of course, the Demiurges choose the best possible option of arranging numbers.

半神沙姆班布克利和马祖克塔喜欢观看凡人的游戏。今天，他们注意到两个人正在玩以下游戏。

有一棵包含 $n$ 个节点的有根树，其中 $m$ 个是叶子节点（即没有子节点的节点），树的边由父节点指向子节点。在树的叶子节点上放置了从 $1$ 到 $m$ 的整数，每个数字恰好出现在一个叶子节点上。

初始时，棋子位于树的根节点。两名玩家轮流移动该棋子；每次移动时，玩家将棋子从当前节点移至其某个子节点；若某玩家无法进行移动，则游戏立即结束。游戏的结果为棋子最终停留的叶子节点上所放置的数字。先手玩家的目标是最大化游戏结果，而后手玩家则相反，目标是最小化游戏结果。我们假设双方均以最优策略进行游戏。

半神拥有全知全能之力，因此可在游戏开始前任意重排叶子节点上的数字。沙姆班布克利希望重排数字，使得双方均以最优策略进行游戏时所得结果尽可能大；而马祖克塔则希望该结果尽可能小。若由沙姆班布克利来重排数字，游戏结果会是多少？若由马祖克塔来重排数字，结果又会是多少？当然，两位半神都会选择能使各自目标最优化的数字排列方式。

The first line contains a single integer n — the number of nodes in the tree (1 ≤ n ≤ 2·105).

Each of the next n - 1 lines contains two integers u__i and v__i (1 ≤ u__i, v__i ≤ n) — the ends of the edge of the tree; the edge leads from node u__i to node v__i. It is guaranteed that the described graph is a rooted tree, and the root is the node 1.

第一行包含一个整数 $n$ —— 树中节点的数量（$1 \leq n \leq 2\cdot10^5$）。

接下来的 $n - 1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$）—— 树中一条边的两个端点；该边从节点 $u_i$ 指向节点 $v_i$。保证所描述的图是一棵有根树，且根节点为节点 $1$。

Print two space-separated integers — the maximum possible and the minimum possible result of the game.

输出两个用空格分隔的整数——游戏可能得到的最大结果和最小结果。

Consider the first sample. The tree contains three leaves: 3, 4 and 5. If we put the maximum number 3 at node 3, then the first player moves there and the result will be 3. On the other hand, it is easy to see that for any rearrangement the first player can guarantee the result of at least 2.

In the second sample no matter what the arragment is the first player can go along the path that ends with a leaf with number 3.

考虑第一个样例。该树包含三个叶子节点：3、4 和 5。如果我们把最大数 3 放在节点 3 上，则先手玩家将移动到该节点，最终结果为 3。另一方面，容易看出：对于任意一种排列方式，先手玩家均能保证至少获得 2 的结果。

在第二个样例中，无论怎样排列，先手玩家总可以沿着一条通向编号为 3 的叶子节点的路径行进。