Nhà hàng IT

Thành phố có $n$ ngã tư được nối với nhau bởi $n-1$ con đường hai chiều tạo thành một cây (đồ thị vô hướng, liên thông, không có chu trình).

Người ta muốn xây các nhà hàng của hai chuỗi khác nhau — gọi là chuỗi $A$ và chuỗi $B$ — tại các ngã tư. Việc xây phải thỏa mãn:

• Mỗi ngã tư có nhiều nhất một nhà hàng.
• Mỗi nhà hàng thuộc đúng một trong hai chuỗi $A$ hoặc $B$.
• Cả hai chuỗi $A$ và $B$ đều phải có ít nhất một nhà hàng.
• Không tồn tại hai ngã tư kề nhau (nối trực tiếp bằng một con đường) mà lại chứa nhà hàng của hai chuỗi khác nhau.

Gọi $a$ là số nhà hàng của chuỗi $A$ và $b$ là số nhà hàng của chuỗi $B$. Cần chọn cách xây sao cho $a+b$ đạt giá trị lớn nhất có thể.

Hãy tìm tất cả các cặp $(a,b)$ hợp lệ đạt được tổng $a+b$ lớn nhất, và in ra theo thứ tự tăng dần của $a$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số ngã tư.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i,y_i$ ($1\le x_i,y_i\le n$) mô tả một con đường nối hai ngã tư $x_i$ và $y_i$.

Dữ liệu bảo đảm đồ thị được cho là một cây có $n$ đỉnh.

Dữ liệu ra

• Dòng đầu in số nguyên $z$ — số cặp $(a,b)$ tìm được.
• $z$ dòng tiếp theo, mỗi dòng in hai số $a$ và $b$ theo thứ tự $a$ tăng dần.

Ràng buộc

• $3\le n\le 5000$

Ví dụ