Codeforces Round 633 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

constructive algorithms

dfs and similar

greedy

math

trees

*1800

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Edge Weight Assignment

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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 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.

Input

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.

Output

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.

Examples

Input

6 1 3 2 3 3 4 4 5 5 6

Output

1 4

Input

6 1 3 2 3 3 4 4 5 4 6

Output

3 3

Input

7 1 2 2 7 3 4 4 7 5 6 6 7

Output

1 6

Note

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/09/2024 08:26:15 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|