A network of n routers, labelled 0 .. n - 1, is wired as a tree: edges holds n - 1 pairs [a, b], each a cable between routers a and b, and every router can reach every other one. If you pick one router as the root, the tree's height is the number of cables on the longest path from the root down to any router.
Write best_roots(n: int, edges: list[list[int]]) -> list[int] that returns every router which, chosen as the root, gives the smallest possible height, in ascending order.
best_roots(7, [[0, 1], [1, 2], [2, 3], [3, 4], [2, 5], [5, 6]]) # [2] height 2
best_roots(8, [[i, i + 1] for i in range(7)]) # [3, 4] a straight line of 8
best_roots(6, [[4, 0], [4, 1], [4, 2], [4, 3], [4, 5]]) # [4]
best_roots(1, []) # [0]
Constraints: 1 <= n <= 10^5, and edges always forms a tree. The tests include a straight line of 100,000 routers, which overflows Python's recursion limit (about 1,000 frames) if you recurse along it.
Measuring the height from every possible root is O(n²), too slow here; aim for O(n).
Show hint
A router at the end of a branch (touching one cable) is never a better root than its neighbour. Strip every such router off at once, and keep going until at most two remain.