Alice dan Bob memiliki sebuah pohon $T$ yang terdiri dari $2N$ simpul yang dinomori dari $1$ hingga $2N$.

Bob memiliki sebuah bilangan bulat $K$, dan ingin mencari $N$ pasangan $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ sehingga setiap bilangan bulat dari $1$ hingga $2N$ muncul tepat pada satu pasangan dan jumlah jarak $\sum_{i=1}^N \text{dist}(X_i, Y_i) = K$, dengan $\text{dist}(X_i, Y_i)$ menyatakan jarak antara simpul $X_i$ dan $Y_i$ pada pohon, yaitu banyaknya sisi pada lintasan (unik) antara $X_i$ dan $Y_i$.

Alice tidak ingin Bob berhasil. Ia dapat melakukan operasi berikut:

• Menghapus sebuah sisi $(U, V)$ dari $T$.
• Menambahkan sebuah sisi baru $(A, B)$ sehingga $T$ tetap merupakan sebuah pohon.

Perhatikan bahwa diperbolehkan memilih sisi yang sama untuk dihapus sekaligus dimasukkan kembali, yang hanya akan menghasilkan pohon semula.

Bantulah Alice mencari sebuah sisi $(U, V)$ yang harus dihapus dan sebuah sisi $(A, B)$ yang harus ditambahkan. Jika terdapat beberapa solusi, Anda boleh mencari yang mana saja.

Dapat dibuktikan bahwa di bawah batasan masalah ini, selalu mungkin untuk menghapus satu sisi dan menambahkan satu sisi sehingga tidak ada $N$ pasangan $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ di mana setiap bilangan bulat dari $1$ hingga $2N$ muncul tepat pada satu pasangan dan jumlah jaraknya sama dengan $K$.

Masukan

Masukan diberikan dalam format berikut:

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

• Semua nilai masukan adalah bilangan bulat.
• $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$
• Dijamin bahwa sisi-sisi yang diberikan membentuk sebuah pohon.
• Dijamin bahwa jumlah $N$ di seluruh kasus uji tidak melebihi $2 \times 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan dua baris:

Baris pertama harus berisi dua bilangan bulat $U$ dan $V$ — yang berarti sisi $(U, V)$ akan dihapus.

Baris kedua harus berisi dua bilangan bulat $A$ dan $B$ — yang berarti sisi $(A, B)$ akan ditambahkan.

Jika terdapat beberapa solusi, cetak yang mana saja.

Contoh

Masukan 1

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

Keluaran 1

1 2
1 2
1 2
1 3

Catatan

Kasus uji 1: Pohon awal sudah tidak memiliki cara bagi Bob untuk memperoleh skor $K = 20$, sehingga Alice cukup menghapus dan memasukkan kembali sisi mana pun yang sudah ada.

Kasus uji 2: Pada pohon awal, terdapat cara bagi Bob untuk memperoleh skor $K = 4$, misalnya dengan memilih pasangan $(1, 4)$ dan $(2, 3)$. Alice menghapus sisi $(1, 2)$ dan memasukkan $(1, 3)$. Pada pohon baru ini, Bob tidak dapat memperoleh skor $4$.