CF581F.Zublicanes and Mumocrates

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

It's election time in Berland. The favorites are of course parties of zublicanes and mumocrates. The election campaigns of both parties include numerous demonstrations on nn main squares of the capital of Berland. Each of the nn squares certainly can have demonstrations of only one party, otherwise it could lead to riots. On the other hand, both parties have applied to host a huge number of demonstrations, so that on all squares demonstrations must be held. Now the capital management will distribute the area between the two parties.

Some pairs of squares are connected by (n1)(n-1) bidirectional roads such that between any pair of squares there is a unique way to get from one square to another. Some squares are on the outskirts of the capital meaning that they are connected by a road with only one other square, such squares are called dead end squares.

The mayor of the capital instructed to distribute all the squares between the parties so that the dead end squares had the same number of demonstrations of the first and the second party. It is guaranteed that the number of dead end squares of the city is even.

To prevent possible conflicts between the zublicanes and the mumocrates it was decided to minimize the number of roads connecting the squares with the distinct parties. You, as a developer of the department of distributing squares, should determine this smallest number.

输入格式

The first line of the input contains a single integer nn ( 2<=n<=50002<=n<=5000 ) — the number of squares in the capital of Berland.

Next n1n-1 lines contain the pairs of integers x,yx,y ( 1<=x,y<=n,xy1<=x,y<=n,x≠y ) — the numbers of the squares connected by the road. All squares are numbered with integers from 11 to nn . It is guaranteed that the number of dead end squares of the city is even.

输出格式

Print a single number — the minimum number of roads connecting the squares with demonstrations of different parties.

输入输出样例

  • 输入#1

    8
    1 4
    2 4
    3 4
    6 5
    7 5
    8 5
    4 5
    

    输出#1

    1
    
  • 输入#2

    5
    1 2
    1 3
    1 4
    1 5
    

    输出#2

    2
    
首页