Ini adalah soal multi-tahap (multi-pass problem).

Di dalam arsip digital Kivotos, Plana telah menemukan sekumpulan catatan misterius yang dikenal sebagai Log Bitemporal. Setiap log terdiri atas $n$ entri berlabel $1$ sampai $n$ yang membentuk sebuah pohon berakar. Namun, batasan strukturalnya berbeda bergantung pada apakah aliran waktunya bersifat retrospektif (Logika A) atau prospektif (Logika B):

• Logika A: Pohon berakar pada entri $1$; setiap entri lainnya $i$ memiliki induk $p_i$ sedemikian sehingga $p_i < i$.
• Logika B: Pohon berakar pada entri $n$; setiap entri lainnya $i$ memiliki induk $q_i$ sedemikian sehingga $q_i > i$.

Untuk menganalisis sifat strukturalnya, Plana mendefinisikan dua jenis entri:

• Terminal: Entri yang tidak menjadi induk bagi entri lain mana pun.
• Hub: Entri yang menjadi induk bagi setidaknya satu entri lain.

Plana mengamati sebuah simetri sempurna yang disebut Resonansi Logis (Logical Resonance). Sifat ini berlaku di antara sebuah log Logika A dan sebuah log Logika B jika dan hanya jika:

$$\text{For every } i\text{, entry } i \text{ is a Terminal in Logic A} \iff \text{entry } i \text{ is a Hub in Logic B.}$$

Plana telah membuktikan secara matematis bahwa banyaknya log Logika A dan log Logika B yang valid di bawah batasan ini adalah identik. Kini, ia menugaskan Anda untuk merancang sebuah Protokol Penerjemahan Universal — sebuah bijeksi — untuk mengubah satu format log ke format lainnya.

Evaluasi Kebenaran

Solusi Anda dijalankan dua kali pada setiap pengujian. Pada eksekusi pertama, solusi Anda harus mengubah setiap log Logika A menjadi sebuah log Logika B yang memenuhi syarat Resonansi Logis. Pada eksekusi kedua, diberikan sebuah log Logika B yang dihasilkan oleh eksekusi pertama Anda, solusi Anda harus memulihkan log Logika A aslinya secara persis.

Masukan dari eksekusi kedua terdiri atas log-log Logika B yang sama dengan keluaran Anda dari eksekusi pertama, mungkin dalam urutan yang berbeda. Untuk setiap masukan log Logika B pada eksekusi kedua, Anda harus mengeluarkan log Logika A yang bersesuaian. Solusi Anda dianggap benar jika, untuk setiap log Logika B tersebut, keluaran Anda persis sama dengan log Logika A yang menghasilkannya pada eksekusi pertama.

Sebuah alat penguji disediakan untuk membantu Anda mengembangkan dan menguji solusi Anda.

Masukan

Baris pertama masukan berisi dua bilangan bulat $r$ ($r \in \{1, 2\}$) dan $T$ ($1 \le T \le 10^5$), yang merepresentasikan nomor eksekusi dan banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama berisi sebuah bilangan bulat $n$ ($2 \le n \le 10^3$).

Jika $r = 1$, baris kedua berisi $n$ bilangan bulat $p_1, p_2, \dots, p_n$ yang merepresentasikan log Logika A. Dijamin bahwa $p_1 = 0$, dan untuk $2 \le i \le n$, $1 \le p_i < i$ adalah entri tempat entri $i$ terhubung. Di sini kita menggunakan $0$ untuk menyatakan bahwa suatu entri tidak memiliki induk (yaitu merupakan akar).

Sebaliknya, jika $r = 2$, baris kedua berisi $n$ bilangan bulat $q_1, q_2, \dots, q_n$ yang merepresentasikan log Logika B. Dijamin bahwa $q_n = 0$, dan untuk $1 \le i \le n - 1$, $i < q_i \le n$ adalah entri tempat entri $i$ terhubung.

Dijamin bahwa jumlah $n^2$ di seluruh kasus uji tidak melebihi $10^7$.

Keluaran

Jika $r = 1$, untuk setiap kasus uji, keluarkan $n$ bilangan bulat yang dipisahkan oleh spasi, $q_1, q_2, \dots, q_n$, yang merepresentasikan log Logika B hasil konversi. Harus berlaku bahwa $q_n = 0$, dan untuk $1 \le i \le n - 1$, $i < q_i \le n$. Sifat Resonansi Logis harus terpenuhi: entri $i$ adalah Terminal pada Logika A jika dan hanya jika entri $i$ adalah Hub pada Logika B.

Sebaliknya, jika $r = 2$, untuk setiap kasus uji, keluarkan $n$ bilangan bulat yang dipisahkan oleh spasi, $p_1, p_2, \dots, p_n$, yang merepresentasikan log Logika A yang telah dipulihkan.

Contoh

Contoh 1, Tahap 1

Masukan

1 3
4
0 1 1 2
4
0 1 2 1
4
0 1 1 1

Keluaran

3 3 4 0
3 4 4 0
2 3 4 0

Contoh 1, Tahap 2

Masukan

2 3
4
2 3 4 0
4
3 3 4 0
4
3 4 4 0

Keluaran

0 1 1 1
0 1 1 2
0 1 2 1

Penjelasan Contoh 1

Salah satu bijeksi valid yang mungkin ditunjukkan di bawah ini.