Minimum Height Trees

Given a tree of n nodes labeled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [a_i, b_i] indicates an undirected edge between nodes a_i and b_i, find all root labels that minimize the height of the tree. You can choose any node as the root. The height of a rooted tree is the number of edges on the longest downward path from the root to a leaf.

Return a list of all Minimum Height Tree (MHT) root labels. You may return the answer in any order.

Examples

Example 1

Input: n = 4, edges = [[1,0],[1,2],[1,3]]

Output: [1]

Explanation: When node 1 is chosen as the root, the tree has height 1, which is the minimum possible. Any other root gives a height of 2.

Example 2

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

Output: [3,4]

Explanation: Both node 3 and node 4 produce trees of height 2, which is the minimum possible.

Constraints

• 1 <= n <= 2 * 10^4
• edges.length == n - 1
• 0 <= a_i, b_i < n
• a_i != b_i
• All pairs (a_i, b_i) are distinct.
• The given input is guaranteed to be a tree.