← 返回 uber 的题目列表Choose a Root to Minimize Edge Reversals (Make All Edges Point Outward)
类型：online_judge
You are given a directed graph with n nodes labeled 1..n and n-1 directed edges. If you ignore directions, the underlying undirected graph is a tree.
You may reverse the direction of any edge at cost 1 per edge.
Choose a root node r and reverse the minimum number of edges so that all edges point outward from r (i.e., every edge is directed from parent to child in the rooted tree).
Return the minimum possible number of reversals over all choices of r.
Input format
Line 1: integer n
Next n-1 lines: two integers u v meaning a directed edge u -> v
Output format
One integer: the global minimum reversals.
Constraints
1 <= n <= 2*10^5
Sample tests (stdin/stdout)
input
3
1 2
3 2
output
0
input
4
1 2
2 3
4 3
output
1
input
5
1 2
1 3
4 1
5 4
output
0
input
2
2 1
output
0
input
6
1 2
2 3
2 4
5 2
6 5
output
0
Example
Input
3
1 2
3 2
Output
0