您有 $$$n$$$ 个顶点的未加权树。您必须为每条边分配正权重,以便满足以下条件:
- 对于该树的每两个不同的叶子 $$$v_{1}$$$ 和 $$$v_{2}$$$,$$$v_{1}$$$ 和 $$$v_{2}$$$ 之间的简单路径上所有边的权重按位异或必须等于 $$$0$$$。
请注意,您可以输入非常大的正整数(例如 $$$10^{(10^{10})}$$$)。
保证在给定的约束下此类分配始终存在。现在让我们将 $$$f$$$ 定义为分配中不同权重的数量。
在此示例中,分配是有效的,因为每对叶子之间的所有边权重的按位异或为 $$$0$$$。这里$$$f$$$ 值为$$$2$$$,因为有$$$2$$$ 不同的边权重($$$4$$$ 和$$$5$$$)。在此示例中,分配无效,因为顶点 $$$1$$$ 和顶点 $$$6$$$ ($$$3, 4, 5, 4$$$) 之间的所有边权重的按位异或不是 $$$0$$$。
给定树的 $$$f$$$ 的最小和最大可能值是多少?查找并打印两者。
输入
第一行包含整数 $$$n$$$ ($$$3 \le n \le 10^{5}$$$) — 给定树中的顶点数。
接下来的 $$$n-1$$$ 行中的第 $$$i$$$ 包含两个整数 $$$a_{i}$$$ 和 $$$b_{i}$$$ ($$$1 \le a_{i} \lt b_{i} \le n$$$) - 这意味着 $$$a_{i}$$$ 和 $$$a_{i}$$$ 之间有一条边$$$b_{i}$$$。保证给定的图形成 $$$n$$$ 个顶点的树。
输出
打印两个整数 - $$$f$$$ 的最小和最大可能值可以通过给定树的有效分配得出。请注意,在给定的约束下总是可以进行分配。
示例
输入 #1
6 1 3 2 3 3 4 4 5 5 6
输出 #1
1 4
输入 #2
6 1 3 2 3 3 4 4 5 4 6
输出 #2
3 3
输入 #3
7 1 2 2 7 3 4 4 7 5 6 6 7
输出 #3
1 6
注意
在第一个示例中,下图描述了每个最小值和最大值的可能分配。当然,每个最小值和最大值都有多种可能的分配。
在第二个示例中,每个最小值和最大值的可能分配如下图所示。该树的有效赋值 $$$f$$$ 值始终为 $$$3$$$。
在第三个示例中,下图描述了每个最小值和最大值的可能分配。当然,每个最小值和最大值都有多种可能的分配。