Krtica

두더지는 깔끔하고 부지런한 동물이다. 우리의 두더지는 지하 저택을 최대한 잘 정돈해 두어, 그곳에 사는 모두가 물건이 어디 있는지 알 수 있게 하고 싶어 한다.
이를 위해 두더지는 방들을 굴로 연결하되, 어떤 방에서 다른 어떤 방으로든 가는 방법이 정확히 하나만 존재하게 했다. 두 방 사이의 거리는 한 방에서 다른 방으로 가는 길에 지나는 홀의 개수이다.
이 모든 노력에도 불구하고, 두더지의 손님 몇몇은 특정 방 쌍 사이를 걷는 데 시간이 너무 오래 걸린다고 불평한다.
두더지는 저택을 개조하기로 했다. 굴 하나를 닫고 새 굴 하나를 열어, 가장 먼 두 방 사이의 거리가 최소가 되게 하되, 여전히 모든 방에서 다른 모든 방으로 갈 수 있어야 한다.
개조 후 가장 먼 두 방 사이의 거리, 닫을 굴과 열 굴을 결정하는 프로그램을 작성하시오.

첫째 줄에 방의 개수인 정수 \(N\) (\(1 \le N \le 300\,000\))이 주어진다. 방에는 \(1\)부터 \(N\)까지 번호가 붙어 있다.

다음 \(N-1\)개의 줄에는 두 정수, 즉 굴이 연결하는 방들의 번호가 주어진다.

다음을 순서대로 각각 다른 줄에 출력한다:

• 개조 후 가장 먼 두 방 사이의 거리.
• 닫아야 할, 기존에 존재하던 굴을 나타내는 정수 쌍.
• 새 굴을 열어야 할 두 방을 나타내는 정수 쌍.

참고: 해는 유일하지 않을 수 있다. 가장 먼 두 방 사이의 거리가 최소가 되는 개조 계획이면 무엇이든 출력해도 된다.

채점: 전체 점수의 \(40\%\)에 해당하는 테스트 케이스에서는 \(N\)이 \(30\)보다 작다. 전체 점수의 \(70\%\)에 해당하는 테스트 케이스에서는 \(N\)이 \(3000\)보다 작다. 또한 출력의 첫째 줄이 올바르고 나머지 두 줄이 없거나 틀렸으면, 해당 테스트 케이스 배점의 약 \(70\%\)를 받는다.

riseoj 작성

출처 COCI 2008/2009 Contest 1