CF1338D.Nested Rubber Bands

普及/提高-

通过率:0%

AC君温馨提醒

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

题目描述

You have a tree of nn vertices. You are going to convert this tree into nn rubber bands on infinitely large plane. Conversion rule follows:

  • For every pair of vertices aa and bb , rubber bands aa and bb should intersect if and only if there is an edge exists between aa and bb in the tree.
  • Shape of rubber bands must be a simple loop. In other words, rubber band is a loop which doesn't self-intersect.

Now let's define following things:

  • Rubber band aa includes rubber band bb , if and only if rubber band bb is in rubber band aa 's area, and they don't intersect each other.
  • Sequence of rubber bands a1,a2,,aka_{1}, a_{2}, \ldots, a_{k} ( k2k \ge 2 ) are nested, if and only if for all ii ( 2ik2 \le i \le k ), ai1a_{i-1} includes aia_{i} .

This is an example of conversion. Note that rubber bands 55 and 66 are nested. It can be proved that is it possible to make a conversion and sequence of nested rubber bands under given constraints.

What is the maximum length of sequence of nested rubber bands can be obtained from given tree? Find and print it.

输入格式

The first line contains integer nn ( 3n1053 \le n \le 10^{5} ) — the number of vertices in tree.

The ii -th of the next n1n-1 lines contains two integers aia_{i} and bib_{i} ( 1ai<bin1 \le a_{i} \lt b_{i} \le n ) — it means there is an edge between aia_{i} and bib_{i} . It is guaranteed that given graph forms tree of nn vertices.

输出格式

Print the answer.

输入输出样例

  • 输入#1

    6
    1 3
    2 3
    3 4
    4 5
    4 6

    输出#1

    4
  • 输入#2

    4
    1 2
    2 3
    3 4

    输出#2

    2

说明/提示

In the first sample, you can obtain a nested sequence of 44 rubber bands( 11 , 22 , 55 , and 66 ) by the conversion shown below. Of course, there are other conversions exist to make a nested sequence of 44 rubber bands. However, you cannot make sequence of 55 or more nested rubber bands with given tree.

You can see one of the possible conversions for the second sample below.

首页