Ini adalah soal multi-pass (dua kali jalan).

VegiCat dan VegiDog memainkan sebuah permainan dengan sebuah hutan yang terdiri dari $n$ verteks, dinomori dari $1$ hingga $n$, dan $m$ sisi. Sebuah hutan adalah graf tak berarah yang tidak memiliki siklus. Hutan tersebut belum tentu terhubung.

Pada tahap pertama, VegiCat menetapkan sebuah bilangan bulat $a_u$ ($1 \le a_u \le 2n$) pada setiap verteks $u$. Nilai-nilai tersebut boleh berulang.

Setelah VegiCat selesai menetapkan nilai-nilai tersebut, verteks-verteksnya dinomori ulang. Misalkan $p_1, p_2, \ldots, p_n$ adalah suatu permutasi dari $1, 2, \ldots, n$, di mana setiap bilangan bulat dari $1$ hingga $n$ muncul tepat satu kali. Untuk setiap $u$, verteks yang semula bernomor $u$ kini bernomor $p_u$.

Setiap sisi $(u, v)$ menjadi $(p_u, p_v)$. Setiap verteks tetap menyimpan nilai yang telah ditetapkan padanya. Misalkan $b_i$ adalah nilai pada verteks $i$ setelah penomoran ulang. Maka $b_{p_u} = a_u$.

Pada tahap kedua, VegiDog hanya menerima $n$ dan $b_1, b_2, \ldots, b_n$, tanpa mengetahui hutan awal maupun $p$. Ia harus memulihkan semua sisi menggunakan nomor-nomor verteks yang baru.

Rancanglah strategi untuk kedua pemain yang berhasil untuk setiap hutan yang valid dan setiap permutasi $p$.

Masukan

Program Anda akan dijalankan dua kali: pertama sebagai VegiCat, kemudian sebagai VegiDog. Kasus-kasus uji muncul dalam urutan yang sama pada kedua eksekusi.

Eksekusi Pertama. Baris pertama berisi string cat, yang menandakan bahwa Anda bermain sebagai VegiCat.

Baris kedua berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^4$), banyaknya kasus uji. Deskripsi dari masing-masing kasus uji menyusul.

Baris pertama dari setiap kasus uji berisi dua bilangan bulat $n$ dan $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m < n$), banyaknya verteks dan sisi.

Masing-masing dari $m$ baris berikutnya berisi dua bilangan bulat $u$ dan $v$ ($1 \le u, v \le n$, $u \ne v$), yang mendeskripsikan sebuah sisi tak berarah antara verteks $u$ dan $v$.

Dijamin bahwa graf tidak memiliki siklus maupun sisi ganda.

Dijamin bahwa jumlah nilai $n$ di seluruh kasus uji tidak melebihi $2 \cdot 10^5$.

Eksekusi Kedua. Baris pertama berisi string dog, yang menandakan bahwa Anda bermain sebagai VegiDog.

Baris kedua berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^4$), banyaknya kasus uji. Deskripsi dari masing-masing kasus uji menyusul.

Baris pertama dari setiap kasus uji berisi sebuah bilangan bulat $n$ ($1 \le n \le 2 \cdot 10^5$), banyaknya verteks.

Baris kedua berisi $n$ bilangan bulat $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 2n$), nilai-nilai yang ditetapkan dalam urutan verteks yang baru.

Dijamin bahwa jumlah nilai $n$ di seluruh kasus uji tidak melebihi $2 \cdot 10^5$.

Keluaran

Eksekusi Pertama. Untuk setiap kasus uji, keluarkan $n$ bilangan bulat $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2n$) dalam satu baris. Bilangan bulat $a_i$ adalah nilai yang ditetapkan pada verteks $i$.

Eksekusi Kedua. Untuk setiap kasus uji, keluarkan sebuah bilangan bulat $m$ pada baris pertama, yaitu banyaknya sisi. Masing-masing dari $m$ baris berikutnya harus berisi dua bilangan bulat $u$ dan $v$ ($1 \le u, v \le n$, $u \ne v$), yang mendeskripsikan sebuah sisi menggunakan nomor-nomor verteks yang baru.

Keluarkan setiap sisi satu kali, dalam urutan apa pun. Titik ujung mana pun boleh ditulis lebih dulu. Jika $m = 0$, cukup keluarkan $0$.

Contoh

Masukan 1

cat
4
1 0
4 3
1 2
4 3
2 3
7 2
6 4
7 1
10 7
10 9
7 9
10 5
4 8
3 7
4 10
1 2

Keluaran 1

1
2 5 8 5
11 11 4 11 3 7 2
10 13 12 5 3 2 16 6 19 3

Masukan 2

dog
4
1
1
4
5 2 5 8
7
11 7 2 11 11 3 4
10
16 3 13 5 10 12 19 6 2 3

Keluaran 2

0
3
1 4
2 1
4 3
2
4 3
5 2
7
1 7
4 8
5 3
6 1
7 10
10 2
10 4

Catatan

Pada kasus uji pertama, hutan memiliki satu verteks dan tidak ada sisi. VegiCat menetapkan nilai $1$ pada verteks tersebut, dan VegiDog mengeluarkan $0$.

Pada kasus uji terakhir, permutasinya adalah $p = [5, 3, 6, 4, 2, 9, 1, 8, 7, 10]$.

VegiCat menetapkan $a_7 = 16$. Karena $p_7 = 1$, VegiDog menerima $b_1 = 16$.

Sisi awal $(3, 7)$ menjadi $(p_3, p_7) = (6, 1)$.

Sisi awal $(4, 10)$ menjadi $(p_4, p_{10}) = (4, 10)$. Contoh keluaran menuliskan sisi ini sebagai $(10, 4)$, yang merepresentasikan sisi tak berarah yang sama.

Contoh tersebut mengilustrasikan format masukan dan keluaran. Keluarannya benar untuk graf dan permutasi yang ditampilkan. Namun, penetapan nilai pada contoh tidak dijamin merupakan bagian dari strategi yang berhasil untuk setiap hutan yang valid dan setiap permutasi.