Tree Diameter

You are given a tree with n nodes. The tree is represented by n - 1 edges connecting the nodes. The diameter of a tree is the length of the longest path between any two nodes.

In this problem you must compute the tree's diameter. Recall that the tree diameter can be computed by performing two breadth-first searches (BFS): first, start from an arbitrary node to find the farthest node, and second, start from that farthest node to determine the maximum distance from it. The diameter is the maximum distance obtained in the second BFS.

The distance between two nodes is defined as the number of edges on the simple path connecting them.

This can be represented mathematically as:

\(\text{diameter} = \max_{u,v \in V} d(u,v)\)

where \(d(u,v)\) is the number of edges between nodes \(u\) and \(v\).

inputFormat

The input is given from standard input. The first line contains a single integer n (the number of nodes). Each of the following n - 1 lines contains two integers u and v, indicating there is an edge connecting node u and node v.

outputFormat

Output to standard output a single integer representing the diameter of the tree.

1

0