Longest path in a tree -Spoj

Prerequisite:- DFS,graph implementation,Diameter of Tree

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 a 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

Java Solution :-

import java.util.ArrayList;
import java.util.Scanner;
/**
*
* @author abhishekraj
*/

public class LongestPath {

static int MaxNode;
static int max;
public static void main(String[] args) {

ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
Scanner sc = new Scanner(System.in);
int n =sc.nextInt();
boolean visited[] = new boolean[10000000];

for(int i=0;i<=n;i++)
{
adj.add(new ArrayList<>());
}
for(int i=1;i<n;i++)
{
int u = sc.nextInt();
int v = sc.nextInt();
addEdge(adj,u,v);

}

max=-1;
dfs(1,visited,adj,0); // From the first dfs call we can find farthest node
for(int i=0;i<visited.length;i++)// After visting all the node we have to make unvisited node so that we can call second dfs
{
visited[i]=false;
}
max=-1;
dfs(MaxNode,visited,adj,0);

System.out.println(max);

}


public static void addEdge(ArrayList<ArrayList<Integer>> adj,int u ,int v)
{
adj.get(u).add(v);
adj.get(v).add(u);

}

// Implementation of DFS

public static void dfs (int node ,boolean visited[],ArrayList<ArrayList<Integer>> adj,int d)
{
visited[node]=true;
if(d>max)
{
max=d;
MaxNode=node;
}
for(int it : adj.get(node))
{
if(!visited[it])
{
dfs(it,visited,adj,d+1);
}
}
}
}