题目描述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

出题Author

Staginner

来源Source