두더지
시간 제한1초메모리 제한128 MB
트리에서 간선 하나를 제거하고 새 간선 하나를 추가해 연결을 유지하면서 트리의 지름을 최소화하고 그 결과와 교체할 간선을 출력합니다.
문제
두더지의 집은 N개의 방과 N-1개의 터널로 이루어진 트리입니다. 임의의 두 방 사이에는 항상 정확히 하나의 경로가 있으며, 두 방의 거리는 그 경로에 포함된 터널의 수입니다.
두더지는 터널 하나를 막고 다른 터널 하나를 새로 파려고 합니다. 공사가 끝난 뒤에도 모든 방은 서로 연결되어 있어야 합니다. 가능한 공사 방법 중에서 가장 먼 두 방 사이의 거리를 최소로 만들어야 합니다.
현재 터널 정보가 주어질 때, 공사 후 가능한 최소 거리와 실제로 막을 터널, 새로 만들 터널을 출력하세요.
입력
첫째 줄에 방의 개수 N이 주어집니다. 방은 1번부터 N번까지 번호가 매겨져 있습니다. (3 ≤ N ≤ 300,000)
다음 N-1개 줄에는 서로 터널로 연결된 두 방의 번호가 주어집니다.
출력
첫째 줄에 공사 후 가장 먼 두 방 사이 거리의 최솟값을 출력합니다.
둘째 줄에는 막을 터널이 연결하는 두 방의 번호를 출력합니다.
셋째 줄에는 새로 만들 터널이 연결하는 두 방의 번호를 출력합니다.
정답이 여러 개라면 그중 아무거나 출력해도 됩니다.