题目描述

有一棵有 $n$ 个结点的有根树，其中有 $m$ 个叶子结点。这 $m$ 个叶子从 $1$ 到 $m$ 分别被给予了一个号码，每个叶子的号码都是独一无二的。一开始根节点有一个棋子，两个玩家每次行动将棋子移动到当前节点的一个儿子节点。当棋子被移动到某个叶节点的时候游戏结束，这个叶节点的号码即为该局游戏的权值。先手的玩家要最大化权值，后手的玩家要最小化这个权值。

在两个玩家都无限聪明的情况下，在树的形态已知的情况下，在叶子的编号可以任意安排的情况下，游戏的权值最大和最小分别是多少呢？

输入格式

第一行一个正整数 $n$，表示结点的数量。

接下来 $n-1$ 行，每行有两个正整数 $u,v$，表示树上有一条 $u,v$ 之间的边。

输出格式

输出一行两个非负整数，分别表示权值的最大值和最小值。

5
1 2
1 3
2 4
2 5

3 2

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 2\times 10^5$，$1\leq u,v\leq n$。