1105 : Directed Chain Decomposition

Description

There is a tree with n nodes (labeled 1, 2, …, n) and n − 1 directed edges. We can decompose the tree into several directed chains, and each edge appears in exactly one chain. Now you need to figure out the minimum number of edges that we need to reverse in order to minimize the minimum possible number of directed chains in the decomposition result.

For example, if we have a tree 1 → 2 → 3 ← 4, we can reverse the edge from node 4 to node 3, then the tree can be decomposed into only one directed chain.

Input

There will be at most 200 test cases. Each case begins with one integer n(3 ≤ n ≤ 10⁵), the number of nodes. Each of the following n − 1 lines contains two integers u_i, v_i(1 ≤ u_i, v_i ≤ n, u_i ≠ v_i), denoting a directed edge from node u_i to node v_i. The size of the whole input file does not exceed 8MB.

Output

For each test case, print the minimum possible number of directed chains in the decomposition result, and the minimum number of edges that we need to reverse.

Sample

4
1 2
2 3
4 3
5
2 1
3 1
4 1
5 1
4
1 2
2 3
2 4

1 1
2 2
2 0

Hint

Source

Author

Staginner