Alice và Bob có một cây $T$ gồm $2N$ đỉnh được đánh số từ $1$ đến $2N$.

Bob có một số nguyên $K$, và muốn tìm $N$ cặp $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ sao cho mỗi số nguyên từ $1$ đến $2N$ xuất hiện trong đúng một cặp và tổng khoảng cách $\sum_{i=1}^N \text{dist}(X_i, Y_i) = K$, trong đó $\text{dist}(X_i, Y_i)$ ký hiệu khoảng cách giữa hai đỉnh $X_i$ và $Y_i$ trong cây, tức là số cạnh trên đường đi (duy nhất) giữa $X_i$ và $Y_i$.

Alice không muốn Bob thành công. Cô ấy có thể thực hiện thao tác sau:

• Xóa một cạnh $(U, V)$ khỏi $T$.
• Thêm một cạnh mới $(A, B)$ sao cho $T$ vẫn là một cây.

Lưu ý rằng được phép chọn cùng một cạnh để vừa xóa vừa thêm, điều này sẽ chỉ giữ nguyên cây ban đầu.

Hãy giúp Alice tìm một cạnh $(U, V)$ cần xóa và một cạnh $(A, B)$ cần thêm. Nếu có nhiều lời giải, bạn có thể tìm bất kỳ lời giải nào.

Có thể chứng minh rằng dưới các ràng buộc của bài toán này, luôn có thể xóa một cạnh và thêm một cạnh sao cho không tồn tại $N$ cặp $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ mà mỗi số nguyên từ $1$ đến $2N$ xuất hiện trong đúng một cặp và tổng khoảng cách bằng $K$.

Dữ liệu vào

Dữ liệu vào được cho theo định dạng sau:

$$T$$ $$N\ K$$ $$U_1\ V_1$$ $$U_2\ V_2$$ $$\vdots$$ $$U_{{2N-1}}\ V_{{2N-1}}$$ $$\vdots$$

• Tất cả các giá trị đầu vào đều là số nguyên.
• $1 \le T \le 10^4$
• $2 \le N \le 2 \times 10^5$
• $1 \le K \le 10^{12}$
• $1 \le U_i, V_i \le 2N$
• Đảm bảo rằng các cạnh đã cho tạo thành một cây.
• Đảm bảo rằng tổng của $N$ trong tất cả các bộ dữ liệu không vượt quá $2 \times 10^5$.

Kết quả

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

Dòng thứ nhất chứa hai số nguyên $U$ và $V$ — nghĩa là cạnh $(U, V)$ sẽ bị xóa.

Dòng thứ hai chứa hai số nguyên $A$ và $B$ — nghĩa là cạnh $(A, B)$ sẽ được thêm vào.

Nếu có nhiều lời giải, hãy in ra bất kỳ lời giải nào.

Ví dụ

Dữ liệu vào 1

2
2 20
1 2
2 3
3 4
2 4
1 2
2 3
3 4

Kết quả 1

1 2
1 2
1 2
1 3

Giải thích

Bộ dữ liệu 1: Cây ban đầu vốn đã không có cách nào để Bob đạt được điểm số $K = 20$, vì vậy Alice chỉ cần xóa và thêm lại bất kỳ cạnh hiện có nào.

Bộ dữ liệu 2: Cây ban đầu có cách để Bob đạt được điểm số $K = 4$, ví dụ bằng cách chọn các cặp $(1, 4)$ và $(2, 3)$. Alice xóa cạnh $(1, 2)$ và thêm cạnh $(1, 3)$. Trong cây mới này, Bob không thể đạt được điểm số $4$.