Giải bài trực tuyến

Xây dựng cây

Cho một cây có N đỉnh. Tìm cách xóa đi một cạnh thuộc cây và thêm vào một cạnh mới, sao cho sau đó, độ dài đường đi dài nhất trên cây là nhỏ nhất có thể. Độ dài của một đường đi được tính bằng số cạnh thuộc đường đi đó.

Dữ liệu

Dòng đầu tiên chứa số N (1 ≤ N ≤ 300 000).

N-1 dòng sau, mỗi dòng chứa 2 số nguyên mô tả một cạnh của cây.

Kết quả

• Dòng đầu tiên in ra độ dài nhỏ nhất tìm được.
• Dòng thứ hai ghi 2 số nguyên cho biết cạnh cần xóa.
• Dòng thứ ba ghi 2 số nguyên cho biết cạnh cần thêm vào.

Nếu có nhiều lời giải, chỉ cần in ra một lời giải bất kỳ.Ví dụ

Dữ liệu
4
1 2
2 3
3 4

Kết quả
2
3 4
4 2

Dữ liệu
7
1 3
2 3
2 7
4 3
7 5
3 6

Kết quả
3
2 3
7 3