Furthest City: Tree Diameter Problem

You are given a tree representing a network of cities connected by roads. A tree is an undirected graph in which any two vertices (cities) are connected by exactly one simple path. Given that there are n cities and n-1 roads, your task is to determine the maximum distance between any two cities, where the distance is measured by the number of roads on the shortest path connecting them.

One common strategy to solve this problem is to perform two breadth-first searches (BFS): first, start from an arbitrary city to find the city farthest from it; second, perform a BFS from that farthest city to determine the maximum distance. Mathematically, if the maximum distance (diameter) is denoted by (d), then the answer is (d).

inputFormat

The input is read from standard input. The first line contains an integer (n) representing the number of cities. Each of the next (n-1) lines contains two space-separated integers (u) and (v), indicating that there is a bidirectional road connecting cities (u) and (v).

outputFormat

Output to standard output a single integer representing the maximum distance (the number of roads) between any two cities in the tree.## sample

5
1 2
1 3
2 4
2 5

3