Maximum Caterpillar Subgraph

Consider a tree with n nodes. We say that a subtree is a caterpillar if there exists a simple path, called the spine, such that every vertex in the subtree is either on the spine or directly adjacent to a vertex on the spine. In other words, if you extract a simple path from the tree and then take all vertices adjacent to this path, the induced subgraph is a caterpillar. The larger the number of vertices in this subgraph (i.e. the longer the spine plus its attached leaves) the larger the caterpillar.

Given a tree, your task is to choose a spine (which can be a single vertex or a simple path) and then include every vertex adjacent to some vertex on the spine (and not already on the spine) in order to form a caterpillar. Output the maximum number of vertices that can be obtained in such a caterpillar subgraph.

Note: The tree is undirected and 1-indexed. There is exactly one path between any two vertices. For a chosen spine S, the caterpillar subgraph consists of all vertices in S plus every vertex (not in S) that is adjacent to at least one vertex in S.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 100), the number of nodes of the tree. Each of the following n - 1 lines contains two integers u and v (1 ≤ u, v ≤ n and u ≠ v) which indicates there is an edge between nodes u and v.

outputFormat

Output a single integer representing the maximum possible number of vertices in a caterpillar subgraph extracted from the given tree.

The answer is computed as follows: for any chosen spine S (a simple path in the tree, which may be a single vertex), let U be the set of all vertices not in S that are adjacent to at least one vertex in S. Then the size of the caterpillar is
\( |S| + |U| \).
You must maximize this quantity over all possible choices of spine S.

sample

1

1