Chính phủ Byteland quyết định đã đến lúc kết nối đất nước nhỏ bé của mình với Internet, để mọi người dân có thể tham gia các cuộc thi lập trình và xem video mèo dễ thương. Công ty Internet Optimists Inc. được giao xây dựng mạng trục nối tất cả \(n\) máy tính của Byteland. Các kết nối trực tiếp được đặt giữa từng cặp máy tính sao cho giữa hai máy tính bất kỳ đều có một dãy kết nối nối chúng với nhau.

Byteland không phải một đất nước giàu có, nên để giảm chi phí, mạng được xây dựng dưới dạng một cây, tức là có đúng \(n-1\) kết nối trực tiếp. Mãi về sau người ta mới nhận ra một nhược điểm nghiêm trọng: chỉ cần một kết nối bị đứt, mạng sẽ bị chia cắt, khiến một số máy tính không thể liên lạc với nhau!

Để tăng độ tin cậy, chính phủ quyết định mạng phải chịu được sự cố đứt một kết nối bất kỳ. Hãy giúp Internet Optimists Inc. cải thiện mạng với chi phí thấp nhất. Biết \(n-1\) cặp máy tính đang được nối trực tiếp, hãy tìm số kết nối ít nhất cần thêm để mạng vẫn liên thông khi bất kỳ một kết nối nào bị đứt, đồng thời chỉ ra các kết nối cần thêm.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\) (\(n\ge3\)), là số máy tính của Byteland. Các máy tính được đánh số từ \(1\) đến \(n\).

Mỗi dòng trong \(n-1\) dòng tiếp theo chứa hai số nguyên \(a,b\) (\(1\le a,b\le n\), \(a\ne b\)), mô tả một kết nối trực tiếp giữa máy tính \(a\) và máy tính \(b\). Các kết nối này tạo thành một cây.

Dữ liệu ra

Dòng đầu chứa số nguyên \(k\), là số kết nối ít nhất cần thêm vào mạng.

Mỗi dòng trong \(k\) dòng tiếp theo chứa hai số nguyên \(a,b\) (\(1\le a,b\le n\), \(a\ne b\)), là hai máy tính cần nối bằng một kết nối mới. Có thể in các kết nối theo thứ tự bất kỳ. Nếu có nhiều phương án, hãy in một phương án bất kỳ.

Sau khi thêm các kết nối đã in, mạng phải vẫn liên thông nếu bất kỳ một kết nối nào bị đứt.

Ràng buộc

• \(3\le n\le500\,000\).
• \(1\le a,b\le n\) và \(a\ne b\) với mỗi kết nối.

Phân nhóm

1. 18 điểm: \(n\le10\).
2. 45 điểm: \(n\le2000\).
3. 37 điểm: \(n\le500\,000\).

Ví dụ

6
1 2
2 3
2 4
5 4
6 4

2
1 5
3 6

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

3
1 6
5 7
8 4