Return nodes on a tree diameter path

Problem

You are given an undirected tree with n nodes labeled 0..n-1 (connected, no cycles). The diameter of a tree is the longest simple path between any two nodes.

Return the nodes (in order) along one diameter path (if multiple diameter paths exist, returning any one of them is acceptable).

Input

• Integer n ( 2 <= n <= 2 * 10^5 )
• List of n - 1 edges edges , where each edge is a pair [u, v] with 0 <= u, v < n

Output

• A list/array path containing the node labels along a longest path (diameter), from one endpoint to the other.

Constraints

• The input graph is guaranteed to be a tree.

Example

Input:

• n = 6
• edges = [[0,1],[1,2],[1,3],[3,4],[4,5]]

One valid output:

• [2,1,3,4,5]

Explanation: the longest path has length 4 edges, from node 2 to node 5.