CF1338B.Edge Weight Assignment

You have unweighted tree of $n$ vertices. You have to assign a positive weight to each edge so that the following condition would hold:

• For every two different leaves $v_{1}$ and $v_{2}$ of this tree, bitwise XOR of weights of all edges on the simple path between $v_{1}$ and $v_{2}$ has to be equal to $0$.

Note that you can put very large positive integers (like $10^{(10^{10})}$).

It's guaranteed that such assignment always exists under given constraints. Now let's define $f$ as the number of distinct weights in assignment.

In this example, assignment is valid, because bitwise XOR of all edge weights between every pair of leaves is $0$. $f$ value is $2$ here, because there are $2$ distinct edge weights($4$ and $5$).

In this example, assignment is invalid, because bitwise XOR of all edge weights between vertex $1$ and vertex $6$ ($3, 4, 5, 4$) is not $0$.

What are the minimum and the maximum possible values of $f$ for the given tree? Find and print both.

你有一棵包含 $n$ 个顶点的无权树。你需要为每条边赋予一个正整数权重，使得以下条件成立：

• 对于该树中任意两个不同的叶子节点 $v_{1}$ 和 $v_{2}$，连接 $v_{1}$ 与 $v_{2}$ 的简单路径上所有边的权重的**按位异或（XOR）**结果必须等于 $0$。

注意：你可以使用非常大的正整数（例如 $10^{(10^{10})}$）。

在给定约束下，保证这样的赋权方案总是存在的。现在定义 $f$ 为所赋边权中互不相同的权值个数。

在该示例中，赋权方案是合法的，因为任意两个叶子节点之间路径上所有边权的按位异或均为 $0$。此处 $f = 2$，因为共使用了 $2$ 种不同的边权（$4$ 和 $5$）。

在该示例中，赋权方案是非法的，因为顶点 $1$ 与顶点 $6$ 之间路径上的边权（$3, 4, 5, 4$）的按位异或结果不为 $0$。

对于给定的树，$f$ 的最小可能值和最大可能值分别是多少？请找出并输出这两个值。

The first line contains integer $n$ ($3 \le n \le 10^{5}$) — the number of vertices in given tree.

The $i$-th of the next $n-1$ lines contains two integers $a_{i}$ and $b_{i}$ ($1 \le a_{i} \lt b_{i} \le n$) — it means there is an edge between $a_{i}$ and $b_{i}$. It is guaranteed that given graph forms tree of $n$ vertices.

第一行包含一个整数 $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}$ 与 $b_{i}$ 之间存在一条边。保证所给图构成一棵含有 $n$ 个顶点的树。

Print two integers — the minimum and maximum possible value of $f$ can be made from valid assignment of given tree. Note that it's always possible to make an assignment under given constraints.

输出两个整数——在给定树的有效赋值下，$f$ 可能取得的最小值和最大值。注意：在给定约束条件下，总能找到一种有效赋值。

In the first example, possible assignments for each minimum and maximum are described in picture below. Of course, there are multiple possible assignments for each minimum and maximum.

In the second example, possible assignments for each minimum and maximum are described in picture below. The $f$ value of valid assignment of this tree is always $3$.

In the third example, possible assignments for each minimum and maximum are described in picture below. Of course, there are multiple possible assignments for each minimum and maximum.

在第一个例子中，每个最小值和最大值的可能赋值如下图所示。当然，每个最小值和最大值都有多种可能的赋值方式。

在第二个例子中，每个最小值和最大值的可能赋值如下图所示。该树的有效赋值的 $f$ 值恒为 $3$。

在第三个例子中，每个最小值和最大值的可能赋值如下图所示。当然，每个最小值和最大值都有多种可能的赋值方式。