Problem Statement

There is a tree with $N$ vertices, numbered $1,2,...,N$.

The $i$-th edge connects vertices $a_i$ and $b_i$.

Halc and Sapp play a game using this tree and a piece.

The game proceeds as follows.

• Initially, the piece is on vertex $1$.
• Halc and Sapp alternately move the piece to an adjacent vertex. If there are multiple possible destinations, the player may move to any of them.
• A vertex that has been visited once can never be entered again.
• The game ends when the piece cannot be moved.

Each move of the piece by either player counts as $1$ turn.

Halc tries to maximize the number of turns until the game ends, and Sapp tries to minimize it.

For each of the cases where Halc moves first and where Halc moves second, output the number of turns until the game ends when both players play optimally.

Input

$N$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{N-1}$ $b_{N-1}$

• $1\leqq N\leqq 2\times 10^5$
• $1\leqq a_i,b_i\leqq N$
• The given graph is a tree.
• All input values are integers.

Output

Output 2 lines.

On the first line, output the number of turns when Halc moves first, and on the second line, output the number of turns when Halc moves second.

Sample

6
1 2
2 3
3 4
3 5
5 6

4
3

4
1 2
1 3
1 4

1
1

1

0
0