Cho một cây, hãy thêm nhiều cạnh nhất có thể để đồ thị thu được là một đồ thị xương rồng (cactus graph).

Một đồ thị xương rồng là đồ thị mà mỗi cạnh nằm trong tối đa một chu trình đơn. Đồ thị này không được chứa khuyên (self-loop) hoặc cạnh song song.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $N$, kích thước của cây ($1 \le N \le 200\,000$).

Mỗi dòng trong $N - 1$ dòng tiếp theo chứa hai số nguyên $u$ và $v$ ($1 \le u, v \le N, u \neq v$), biểu thị rằng có một cạnh giữa các nút $u$ và $v$. Đảm bảo rằng đồ thị thu được là một cây.

Dữ liệu ra

Trên dòng đầu tiên, in ra $K$, số lượng cạnh tối đa có thể thêm vào đồ thị. Trên mỗi dòng trong $K$ dòng tiếp theo, in ra hai số nguyên $a$ và $b$ ($1 \le a, b \le N, a \neq b$), biểu thị rằng bạn sẽ thêm một cạnh giữa các nút $a$ và $b$. Đồ thị thu được phải là một đồ thị xương rồng.

Nếu có nhiều lời giải với cùng số lượng $K$ tối đa, hãy in ra bất kỳ lời giải nào trong số đó.

Ví dụ

Dữ liệu vào 1

6
6 4
3 1
3 6
4 5
2 3

Dữ liệu ra 1

2
2 1
3 5