Given an undirected tree, return its diameter: the number of edges in a longest path in that tree.

The tree is given as an array of edges where edges[i] = [u, v] is a bidirectional edge between nodes u and v.  Each node has labels in the set {0, 1, ..., edges.length}.

 

Example 1:



Input: edges = [[0,1],[0,2]]
Output: 2
Explanation: 
A longest path of the tree is the path 1 - 0 - 2.
Example 2:



Input: edges = [[0,1],[1,2],[2,3],[1,4],[4,5]]
Output: 4
Explanation: 
A longest path of the tree is the path 3 - 2 - 1 - 4 - 5.
 

Constraints:

0 <= edges.length < 10^4
edges[i][0] != edges[i][1]
0 <= edges[i][j] <= edges.length
The given edges form an undirected tree.











class Solution {
public:
    bool visit[10010];
    int res=0;
    int treeDiameter(vector<vector<int>>& edges) {
        memset(visit,false,sizeof(visit));
        int n=edges.size()+1;
        vector<vector<int>>graph(n);
        for(vector<int>&A:edges){
            int v1=A[0],v2=A[1];
            graph[v1].push_back(v2);
            graph[v2].push_back(v1);
        }
        visit[1]=true;
        dfs(graph,1);
        return res;
    }
    
    int dfs(vector<vector<int>>&graph,int root){
        
        vector<int>lines;
        vector<int>&childs=graph[root];
        for(int c:childs){
            if(visit[c])continue;
            visit[c]=true;
            int val=dfs(graph,c);
            lines.push_back(val);
        }
        if(lines.size()==0)return 0+1;//leaf
        lines.push_back(0);
        sort(lines.begin(),lines.end());
        res=max(res,lines[lines.size()-1]+lines[lines.size()-2]);
        
        return lines[lines.size()-1]+1;
    }
};