Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-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.

No tag edit access

E. Demiurges Play Again

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputDemiurges Shambambukli and Mazukta love to watch the games of ordinary people. Today, they noticed two men who play the following game.

There is a rooted tree on *n* nodes, *m* of which are leaves (a leaf is a nodes that does not have any children), edges of the tree are directed from parent to children. In the leaves of the tree integers from 1 to *m* are placed in such a way that each number appears exactly in one leaf.

Initially, the root of the tree contains a piece. Two players move this piece in turns, during a move a player moves the piece from its current nodes to one of its children; if the player can not make a move, the game ends immediately. The result of the game is the number placed in the leaf where a piece has completed its movement. The player who makes the first move tries to maximize the result of the game and the second player, on the contrary, tries to minimize the result. We can assume that both players move optimally well.

Demiurges are omnipotent, so before the game they can arbitrarily rearrange the numbers placed in the leaves. Shambambukli wants to rearrange numbers so that the result of the game when both players play optimally well is as large as possible, and Mazukta wants the result to be as small as possible. What will be the outcome of the game, if the numbers are rearranged by Shambambukli, and what will it be if the numbers are rearranged by Mazukta? Of course, the Demiurges choose the best possible option of arranging numbers.

Input

The first line contains a single integer *n* — the number of nodes in the tree (1 ≤ *n* ≤ 2·10^{5}).

Each of the next *n* - 1 lines contains two integers *u*_{i} and *v*_{i} (1 ≤ *u*_{i}, *v*_{i} ≤ *n*) — the ends of the edge of the tree; the edge leads from node *u*_{i} to node *v*_{i}. It is guaranteed that the described graph is a rooted tree, and the root is the node 1.

Output

Print two space-separated integers — the maximum possible and the minimum possible result of the game.

Examples

Input

5

1 2

1 3

2 4

2 5

Output

3 2

Input

6

1 2

1 3

3 4

1 5

5 6

Output

3 3

Note

Consider the first sample. The tree contains three leaves: 3, 4 and 5. If we put the maximum number 3 at node 3, then the first player moves there and the result will be 3. On the other hand, it is easy to see that for any rearrangement the first player can guarantee the result of at least 2.

In the second sample no matter what the arragment is the first player can go along the path that ends with a leaf with number 3.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/15/2018 08:52:58 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|