Mạng lưới của Syrjälä gồm \(n\) máy tính và \(n − 1\) kết nối giữa chúng. Có thể gửi dữ liệu giữa hai máy tính bất kỳ.

Tuy nhiên, nếu bất kỳ kết nối nào bị hỏng, sẽ không còn có thể gửi dữ liệu giữa một số máy tính. Nhiệm vụ của bạn là thêm số lượng kết nối mới tối thiểu theo cách mà bạn vẫn có thể gửi dữ liệu giữa hai máy tính bất kỳ ngay cả khi bất kỳ kết nối đơn lẻ nào bị hỏng.

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng máy tính. Các máy tính được đánh số \(1, 2,\ldots, n\)
• Sau này, có \(n - 1\) dòng mô tả các kết nối. Mỗi dòng có hai số nguyên \(a\) và \(b\): có kết nối giữa các máy tính \(a\) và \(b\)

Output

• Đầu tiên in một số nguyên \(k\): số lượng kết nối mới tối thiểu
• Sau này, in \(k\) dòng biểu thị cho các kết nối. Bạn có thể in bất kỳ giải pháp nào hợp lệ

Constraints

• \(3 \leq n \leq 10^5\)
• \(1 \leq a, b \leq n\)

Example

5
1 2
1 3
3 4
3 5

2
2 4
4 5