Tämä on kaksivaiheinen (multi-pass) tehtävä.

VegiCat ja VegiDog pelaavat peliä metsällä, jossa on $n$ solmua, numeroituina $1$:stä $n$:ään, ja $m$ kaarta. Metsä on suuntaamaton verkko, jossa ei ole syklejä. Se ei ole välttämättä yhtenäinen.

Ensimmäisessä vaiheessa VegiCat asettaa jokaiselle solmulle $u$ kokonaisluvun $a_u$ ($1 \le a_u \le 2n$). Arvot voivat toistua.

Kun VegiCat on saanut arvojen asettamisen valmiiksi, solmut numeroidaan uudelleen. Olkoon $p_1, p_2, \ldots, p_n$ lukujen $1, 2, \ldots, n$ permutaatio, jossa jokainen kokonaisluku $1$:stä $n$:ään esiintyy täsmälleen kerran. Jokaisella $u$ alun perin numerolla $u$ numeroitu solmu on nyt numeroitu luvulla $p_u$.

Jokainen kaari $(u, v)$ muuttuu kaareksi $(p_u, p_v)$. Jokainen solmu säilyttää sille asetetun arvon. Olkoon $b_i$ solmun $i$ arvo uudelleennumeroinnin jälkeen. Tällöin $b_{p_u} = a_u$.

Toisessa vaiheessa VegiDog saa vain luvun $n$ sekä arvot $b_1, b_2, \ldots, b_n$, ilman alkuperäistä metsää tai permutaatiota $p$. Hänen täytyy palauttaa kaikki kaaret käyttäen uusia solmunumeroita.

Suunnittele molemmille pelaajille strategiat, jotka toimivat jokaiselle kelvolliselle metsälle ja jokaiselle permutaatiolle $p$.

Syöte

Ohjelmasi ajetaan kaksi kertaa: ensin VegiCatina, sitten VegiDogina. Testitapaukset esiintyvät samassa järjestyksessä molemmilla ajokerroilla.

Ensimmäinen ajo. Ensimmäinen rivi sisältää merkkijonon cat, mikä osoittaa, että pelaat VegiCatina.

Toinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^4$), testitapausten lukumäärän. Seuraavaksi esitetään testitapausten kuvaukset.

Kunkin testitapauksen ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m < n$), solmujen ja kaarien lukumäärät.

Jokainen seuraavista $m$ rivistä sisältää kaksi kokonaislukua $u$ ja $v$ ($1 \le u, v \le n$, $u \ne v$), jotka kuvaavat suuntaamattoman kaaren solmujen $u$ ja $v$ välillä.

On taattu, että verkossa ei ole syklejä eikä moninkertaisia kaaria.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $2 \cdot 10^5$.

Toinen ajo. Ensimmäinen rivi sisältää merkkijonon dog, mikä osoittaa, että pelaat VegiDogina.

Toinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^4$), testitapausten lukumäärän. Seuraavaksi esitetään testitapausten kuvaukset.

Kunkin testitapauksen ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 2 \cdot 10^5$), solmujen lukumäärän.

Toinen rivi sisältää $n$ kokonaislukua $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 2n$), asetetut arvot uudessa solmujärjestyksessä.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $2 \cdot 10^5$.

Tuloste

Ensimmäinen ajo. Tulosta jokaista testitapausta kohden $n$ kokonaislukua $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2n$) yhdelle riville. Kokonaisluku $a_i$ on solmulle $i$ asetettu arvo.

Toinen ajo. Tulosta jokaista testitapausta kohden ensimmäiselle riville kokonaisluku $m$, kaarien lukumäärä. Jokaisen seuraavista $m$ rivistä on sisällettävä kaksi kokonaislukua $u$ ja $v$ ($1 \le u, v \le n$, $u \ne v$), jotka kuvaavat kaaren käyttäen uusia solmunumeroita.

Tulosta jokainen kaari kerran, missä tahansa järjestyksessä. Kumpi tahansa päätepiste voi olla ensin. Jos $m = 0$, tulosta vain $0$.

Esimerkit

Syöte 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

Tuloste 1

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

Syöte 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

Tuloste 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

Huomautus

Ensimmäisessä testitapauksessa metsässä on yksi solmu eikä yhtään kaarta. VegiCat asettaa solmulle arvon $1$, ja VegiDog tulostaa $0$.

Viimeisessä testitapauksessa permutaatio on $p = [5, 3, 6, 4, 2, 9, 1, 8, 7, 10]$.

VegiCat asettaa $a_7 = 16$. Koska $p_7 = 1$, VegiDog vastaanottaa arvon $b_1 = 16$.

Alkuperäisestä kaaresta $(3, 7)$ tulee $(p_3, p_7) = (6, 1)$.

Alkuperäisestä kaaresta $(4, 10)$ tulee $(p_4, p_{10}) = (4, 10)$. Esimerkki tulostaa tämän kaaren muodossa $(10, 4)$, mikä esittää samaa suuntaamatonta kaarta.

Esimerkki havainnollistaa syöte- ja tulostemuotoja. Sen tulosteet ovat oikein esitetyille verkoille ja permutaatioille. Ei kuitenkaan ole taattua, että esimerkin arvojen asetukset ovat osa strategiaa, joka toimii jokaiselle kelvolliselle metsälle ja jokaiselle permutaatiolle.