Problem 21: Longest Path in a Tree

Problem Statement: Given an unrooted tree with n nodes, find the length (number of edges) of the tree's diameter (the longest distance between any two nodes).

Input

The first line contains an integer n (number of nodes). Each of the next n-1 lines contains two integers u and v denoting an edge between nodes u and v.

Output

Print the diameter of the tree.

Examples


Input:
5
1 2
1 3
3 4
3 5

Output:
3

Solution Explanation

Method 1: Use two DFS traversals. First, run DFS from an arbitrary node to find the farthest node u; then run DFS from u to find the farthest node from it; the distance is the diameter. Method 2: Use BFS twice instead of DFS, which can also determine the tree diameter efficiently.

Solution in C++


#include 
using namespace std;

int n;
vector adj[200005];

pair dfs(int u, int parent) {
    pair res = {0, u};
    for (int v : adj[u]) {
        if(v==parent) continue;
        auto p = dfs(v, u);
        p.first++;
        res = max(res, p);
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i < n; i++){
        int u,v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    auto p1 = dfs(1, -1);
    auto p2 = dfs(p1.second, -1);
    cout << p2.first << "
";
    return 0;
}