PT07Z

You are given an unweighted, undirected tree. Write a program to output the length of the longest path (from one node to another) in that tree. The length of a path in this case is number of edges we traverse from source to destination.

Input

The first line of the input file contains one integer N --- number of nodes in the tree (0 < N <= 10000). Next N-1 lines contain N-1 edges of that tree --- Each line contains a pair (u, v) means there is an edge between node u and node v (1 <= u,v <= N).

Output

Print the length of the longest path on one line.

Example

Input:
3
1 2
2 3

Output:
2

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

pair<int, int> longestPath(vector<vector<int> > adj, int source) {  
    int nodes = adj.size();
    deque<int> q;
    vector<bool> visited(nodes, false);
    vector<int> sourceDist(nodes, 0);
    q.push_back(source);
    visited[source] = true;
    while (!q.empty()) {
        int current = q.front();
        q.pop_front();
        for (int i = 0; i < adj[current].size(); ++i) {
            if (!visited[adj[current][i]]) {
                sourceDist[adj[current][i]] = 
                    sourceDist[current] + 1;
                q.push_back(adj[current][i]);
                visited[adj[current][i]] = true;
            }
        }
    }
    int maxIndex = max_element(sourceDist.begin(), 
                   sourceDist.end()) - sourceDist.begin();
    return make_pair(sourceDist[maxIndex], maxIndex);
}

int main() {  
    int nodes;
    cin >> nodes;
    vector<vector<int> > adj(nodes);
    for (int i = 0; i < nodes - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int farthestNode = longestPath(adj, 0).second;
    cout << longestPath(adj, farthestNode).first << "\n";
    return 0;
}