CSG-CPC
Online Judge

# 1105 : Directed Chain Decomposition

Time Limit: 2 Sec     Memory Limit: 128 Mb     Submitted: 2     Solved: 1

## 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 ≤ 105), the number of nodes. Each of the following n − 1 lines contains two integers ui, vi(1 ≤ ui, vi ≤ n, ui ≠ vi), denoting a directed edge from node ui to node vi. 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

Staginner