题目描述

After many weeks of hard work, Bessie is finally getting a vacation! After many weeks of hard work, Bessie is finally getting a vacation! numbered 1..N. The cows have set up quite an unusual road network with exactly N-1 roads connecting pairs of cows C1 and C2 (1 <= C1 <= N; 1 <= C2 <= N; C1 != C2) in such a way that there exists a unique path of roads between any two cows.

FJ wants Bessie to come back to the farm soon; thus, he has instructed Bessie that if two cows are directly connected by a road, she may not visit them both. Of course, Bessie would like her vacation to be as long as possible, so she would like to determine the maximum number of cows she can visit.

经过了几周的辛苦工作,贝茜终于迎来了一个假期.作为奶牛群中最会社交的牛,她希望去拜访N(1<=N<=50000)个朋友.这些朋友被标号为1..N.这些奶牛有一个不同寻常的交通系统,里面有N-1条路,每条路连接了一对编号为C1和C2的奶牛(1 <= C1 <= N; 1 <= C2 <= N; C1<>C2).这样,在每一对奶牛之间都有一条唯一的通路. FJ希望贝茜尽快的回到农场.于是,他就指示贝茜,如果对于一条路直接相连的两个奶牛,贝茜只能拜访其中的一个.当然,贝茜希望她的假期越长越好,所以她想知道她可以拜访的奶牛的最大数目.

输入格式

* Line 1: A single integer: N

* Lines 2..N: Each line describes a single road with two

space-separated integers: C1 and C2

输出格式

* Line 1: A single integer representing the maximum number of cows that Bessie can visit.

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

4 

提示

Bessie knows 7 cows. Cows 6 and 2 are directly connected by a road, as are cows 3 and 4, cows 2 and 3, etc. The illustration below depicts the roads that connect the cows:

1--2--3--4

| 5--6--7

Bessie can visit four cows. The best combinations include two cows on the top row and two on the bottom. She can't visit cow 6 since that would preclude visiting cows 5 and 7; thus she visits 5 and 7. She can also visit two cows on the top row: {1,3}, {1,4}, or {2,4}.