Piggy (người quản lý Ủy ban Giao thức Kết nối Liên sao trong thời gian rảnh rỗi) đang đối mặt với một bài toán phần cứng hóc búa. Mạng lưới liên lạc mới nhất, bao gồm $n$ trạm chuyển tiếp được kết nối bởi $(n - 1)$ liên kết cáp quang tạo thành cấu trúc cây, cuối cùng đã sẵn sàng để triển khai. Tuy nhiên, hệ thống phải được khởi động với sự thận trọng cực độ.

Quá trình kích hoạt bao gồm việc bắn các xung laser dọc theo các đường dẫn cụ thể. Một đường dẫn được định nghĩa là lộ trình đơn duy nhất giữa hai trạm. Do rủi ro thảm khốc của "Nhiễu dòng ngược lượng tử" — một hiện tượng khiến các luật sư của ủy ban mất ngủ — giao thức sau đây phải được tuân thủ nghiêm ngặt:

• Các đường truyền phải được thiết lập lần lượt từng cái một.
• Để ngăn chặn sự tăng vọt điện áp, mỗi đường dẫn mới được thiết lập chỉ được phép chia sẻ tối đa một trạm với tập hợp các trạm đã được kích hoạt bởi bất kỳ đường dẫn nào trước đó.

Về mặt hình thức, gọi $S$ là tập hợp các trạm hiện đang được kích hoạt. Đối với bất kỳ đường dẫn mới $P$ nào bao gồm một tập hợp các trạm $V(P)$, điều kiện $|V(P) \cap S| \le 1$ phải được thỏa mãn. Sau khi một đường dẫn được bắn thành công, tất cả các trạm dọc theo đường dẫn đó được coi là một phần của tập hợp đã kích hoạt $S$.

Nhiệm vụ của bạn, nếu bạn chọn chấp nhận nó, là xác định số lượng xung laser tối thiểu cần thiết để kích hoạt mọi trạm trong toàn bộ mạng lưới và cung cấp một trình tự các đường dẫn như vậy để đáp ứng yêu cầu của bộ phận pháp lý.

Hình minh họa hai trường hợp thử nghiệm mẫu đầu tiên. Lưu ý rằng trong Trường hợp 2, xung thứ hai chỉ chia sẻ trạm 2 với xung thứ nhất, thỏa mãn quy tắc không gây nhiễu.

Dữ liệu vào

Có nhiều trường hợp thử nghiệm. Dòng đầu tiên của dữ liệu vào chứa một số nguyên $T$ ($1 \le T \le 10^4$) biểu thị số lượng trường hợp thử nghiệm. Đối với mỗi trường hợp thử nghiệm:

Dòng đầu tiên chứa một số nguyên $n$ ($2 \le n \le 3 \times 10^5$), số lượng trạm trong lưới.

Đối với $(n - 1)$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $u_i$ và $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), mô tả một liên kết cáp quang hai chiều giữa trạm $u_i$ và trạm $v_i$.

Đảm bảo rằng các liên kết tạo thành một cây và tổng của $n$ trên tất cả các trường hợp thử nghiệm không vượt quá $3 \times 10^5$.

Dữ liệu ra

Đối với mỗi trường hợp thử nghiệm, hãy xuất số lượng đường dẫn tối thiểu $k$ trên dòng đầu tiên. Sau đó, xuất $k$ dòng, mỗi dòng chứa hai số nguyên $a_i$ và $b_i$, đại diện cho các điểm cuối của đường dẫn thứ $i$ trong trình tự. Lưu ý rằng $a_i$ có thể bằng $b_i$ nếu đường dẫn chỉ bao gồm một trạm duy nhất.

Nếu tồn tại nhiều trình tự tối ưu, bất kỳ trình tự nào tuân thủ nghiêm ngặt giao thức không gây nhiễu đều sẽ được chấp nhận.

Ví dụ

Ví dụ 1

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

Ví dụ 2

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