Cắt và nối cạnh để có một trọng tâm

Cho một cây gồm $n$ đỉnh. Một đỉnh được gọi là trọng tâm của cây nếu khi xoá đỉnh đó (cùng mọi cạnh kề với nó), kích thước thành phần liên thông lớn nhất của đồ thị còn lại là nhỏ nhất có thể. Một cây có thể có nhiều hơn một trọng tâm.

Bạn phải thực hiện đúng hai thao tác theo thứ tự: xoá một cạnh của cây, sau đó thêm một cạnh. Đồ thị thu được sau hai thao tác phải là một cây. Được phép thêm lại chính cạnh vừa xoá.

Hãy thực hiện hai thao tác sao cho cây thu được có đúng một trọng tâm. Có thể chứng minh rằng luôn tồn tại cách làm như vậy.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $t$, số bộ dữ liệu.

Mỗi bộ dữ liệu gồm:

• Dòng đầu chứa số nguyên $n$, số đỉnh của cây.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x,y$ thể hiện một cạnh nối đỉnh $x$ và đỉnh $y$.

Dữ liệu đảm bảo đồ thị cho là một cây.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra hai dòng:

• Dòng thứ nhất gồm hai số nguyên $x_1,y_1$: xoá cạnh nối $x_1$ và $y_1$. Cạnh này phải tồn tại trong cây.
• Dòng thứ hai gồm hai số nguyên $x_2,y_2$: thêm cạnh nối $x_2$ và $y_2$.

Nếu có nhiều đáp án, in ra đáp án bất kỳ.

Ràng buộc

• $1\le t\le {10}^4$
• $3\le n\le {10}^5$
• $1\le x,y\le n$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá ${10}^5$.

Ví dụ