#1318. TREEREBLD - Sửa cây

Cho một đồ thị cây gồm nút, các nút đánh số . Khoảng cách giữa hai nút bất kì là số cạnh trên đường đi đơn (duy nhất) nối chúng.

Cần sửa lại cây sao cho khoảng cách giữa hai nút xa nhất là nhỏ nhất có thể. Phép sửa cây là xóa bỏ đúng một cạnh rồi thêm vào đúng một cạnh sao cho đồ thị vẫn là cây. Hãy chỉ ra một cách sửa tối ưu.

Dữ liệu vào:

• Dòng đầu ghi số nguyên ;
• dòng tiếp theo, mỗi dòng ghi hai số nguyên là thể hiện một cạnh của cây.

Dữ liệu ra:

• Dòng đầu ghi đường kính của cây mới;
• Dòng thứ hai ghi hai số nguyên là cạnh bị xóa;
• Dòng ba ghi hai số nguyên là cạnh được thêm;

Nếu có nhiều phương án tối ưu thì chỉ cần đưa ra một trong số chúng.

Ví dụ:

Dữ liệu vào:

4
1 2
2 3
3 4

Dữ liệu ra:

2
3 4
4 2

Dữ liệu vào:

7
1 3
2 3
2 7
4 3
7 5
3 6

Dữ liệu ra:

3
2 3
7 3