Rừng đường kính nhỏ nhất

Cho một rừng — đồ thị vô hướng $n$ đỉnh trong đó mỗi thành phần liên thông là một cây.

Đường kính của một cây liên thông là số cạnh lớn nhất trên đường đi ngắn nhất giữa hai đỉnh bất kỳ của nó.

Bạn cần thêm một số cạnh (có thể bằng $0$) vào rừng sao cho đồ thị thu được là một cây duy nhất và đường kính của cây này nhỏ nhất có thể.

Nếu có nhiều cách thêm cạnh cho cùng kết quả tối ưu, in ra bất kỳ cách nào.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$ — số đỉnh và số cạnh của rừng.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $v$ và $u$ ($1\le v,u\le n$, $v\ne u$) mô tả một cạnh.

Dữ liệu đảm bảo đồ thị đã cho là một rừng.

Dữ liệu ra

• Dòng đầu in ra đường kính của cây thu được.
• $(n-1)-m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $v$ và $u$ mô tả một cạnh được thêm vào ($1\le v,u\le n$, $v\ne u$).

Đồ thị thu được phải là một cây và có đường kính nhỏ nhất có thể. Khi $m=n-1$ (rừng đã là một cây), không cần thêm cạnh nào — chỉ in ra đường kính.

Ràng buộc

• $1\le n\le 1000$
• $0\le m\le n-1$

Ví dụ