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 in C++


#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> adj[200005];

pair<int,int> dfs(int u, int parent) {
    pair<int,int> 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 << "\n";
    return 0;
}