Under construction

Still being built. Things may change

Nested Rubber Bands

Time limit1sMemory limit1024 MB

Summary
Given a tree of n vertices, find the largest set of pairwise non-adjacent vertices that can be nested as rubber bands.
Level

Medium5 of 10

Topics
Tree, Dynamic programming
Solved
No attempts yet

Problem

You have a tree of nn vertices. You are going to convert this tree into nn rubber bands on an infinitely large plane. The conversion follows these rules:

  • For every pair of vertices aa and bb, rubber bands aa and bb intersect if and only if there is an edge between aa and bb in the tree.
  • Each rubber band has the shape of a simple loop. In other words, a rubber band is a loop that does not intersect itself.

We define the following terms:

  • Rubber band aa includes rubber band bb if and only if rubber band bb lies inside the area of rubber band aa and the two do not intersect.
  • A sequence of rubber bands a1,a2,…,aka_1, a_2, \ldots, a_k (k≥2k \ge 2) is nested if and only if for every ii (2≤i≤k2 \le i \le k), ai−1a_{i-1} includes aia_i.

This is an example of a conversion. Rubber bands 55 and 66 are nested.

It can be proved that a conversion and a nested sequence of rubber bands satisfying the constraints always exist.

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

Input

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

The ii-th of the next n−1n-1 lines contains two integers aia_i and bib_i (1≤ai<bi≤n1 \le a_i \lt b_i \le n), meaning there is an edge between aia_i and bib_i. The given graph is guaranteed to be a tree on nn vertices.

Output

Print the answer.

Hint

In the first input, you can obtain a nested sequence of 44 rubber bands (11, 22, 55, and 66) with the conversion shown below. Other conversions also produce a nested sequence of 44 rubber bands. However, no nested sequence of 55 or more rubber bands can be made from this tree.

One possible conversion for the second input is shown below.

Examples2

  1. Example 1

    Input
    6
    1 3
    2 3
    3 4
    4 5
    4 6
    
    Expected output
    4
    
  2. Example 2

    Input
    4
    1 2
    2 3
    3 4
    
    Expected output
    2