Edge Weight Assignment

Time limit1sMemory limit1024 MB

Summary

Given a tree, assign positive edge weights so every leaf-to-leaf path XOR is zero, and find the minimum and maximum count of distinct weights.

Level: Medium6 of 10
Topics: Tree, BFS, Math
Solved: No attempts yet

Problem

You have an unweighted tree with $n$ vertices. Assign a positive weight to each edge so that, for every two different leaves $v_1$ and $v_2$ , the bitwise XOR of the weights of all edges on the simple path between them is $0$ . The weights may be very large positive integers, such as $10^{10^{10}}$ . Such an assignment always exists under the given constraints. Let $f$ be the number of distinct weights in the assignment. Find the minimum and maximum possible values of $f$ for the given tree.

Input

The first line contains an integer $n$ ( $3 \le n \le 10^5$ ), the number of vertices. Each of the next $n-1$ lines contains two integers $a_i$ and $b_i$ ( $1 \le a_i < b_i \le n$ ), meaning there is an edge between $a_i$ and $b_i$ . The given graph is a tree with $n$ vertices.

Output

Print two integers: the minimum and the maximum possible value of $f$ for a valid assignment of the given tree.

Hint

In the first example, the pictures show one assignment for the minimum and one for the maximum. Each value has several valid assignments. In the second example, the value of $f$ is always $3$ . In the third example, the pictures show one assignment for the minimum and one for the maximum, and again several valid assignments exist.

Examples3

Example 1
Input
```
6
1 3
2 3
3 4
4 5
5 6
```
Expected output
```
1 4
```
Example 2
Input
```
6
1 3
2 3
3 4
4 5
4 6
```
Expected output
```
3 3
```
Example 3
Input
```
7
1 2
2 7
3 4
4 7
5 6
6 7
```
Expected output
```
1 6
```