Detta är ett tvåfasproblem (multi-pass).

VegiCat och VegiDog spelar ett spel med en skog med $n$ hörn, numrerade från $1$ till $n$, och $m$ kanter. En skog är en oriktad graf utan cykler. Den är inte nödvändigtvis sammanhängande.

I det första steget tilldelar VegiCat ett heltal $a_u$ ($1 \le a_u \le 2n$) till varje hörn $u$. Värdena får upprepas.

När VegiCat har avslutat tilldelningen av värdena numreras hörnen om. Låt $p_1, p_2, \ldots, p_n$ vara en permutation av $1, 2, \ldots, n$, där varje heltal från $1$ till $n$ förekommer exakt en gång. För varje $u$ får det hörn som ursprungligen hade nummer $u$ nu numret $p_u$.

Varje kant $(u, v)$ blir $(p_u, p_v)$. Varje hörn behåller sitt tilldelade värde. Låt $b_i$ vara värdet i hörn $i$ efter omnumreringen. Då gäller $b_{p_u} = a_u$.

I det andra steget får VegiDog endast $n$ och $b_1, b_2, \ldots, b_n$, utan den ursprungliga skogen eller $p$. Han måste återskapa alla kanter med hjälp av de nya hörnnumren.

Utforma strategier för båda spelarna som fungerar för varje giltig skog och varje permutation $p$.

Indata

Ditt program kommer att köras två gånger: först som VegiCat, sedan som VegiDog. Testfallen förekommer i samma ordning i båda körningarna.

Första körningen. Den första raden innehåller strängen cat, vilket anger att du spelar VegiCat.

Den andra raden innehåller ett heltal $T$ ($1 \le T \le 10^4$), antalet testfall. Beskrivningen av testfallen följer.

Den första raden i varje testfall innehåller två heltal $n$ och $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m < n$), antalet hörn och kanter.

Var och en av de följande $m$ raderna innehåller två heltal $u$ och $v$ ($1 \le u, v \le n$, $u \ne v$), som beskriver en oriktad kant mellan hörnen $u$ och $v$.

Det garanteras att grafen inte har några cykler eller multipelkanter.

Det garanteras att summan av $n$ över alla testfall inte överstiger $2 \cdot 10^5$.

Andra körningen. Den första raden innehåller strängen dog, vilket anger att du spelar VegiDog.

Den andra raden innehåller ett heltal $T$ ($1 \le T \le 10^4$), antalet testfall. Beskrivningen av testfallen följer.

Den första raden i varje testfall innehåller ett heltal $n$ ($1 \le n \le 2 \cdot 10^5$), antalet hörn.

Den andra raden innehåller $n$ heltal $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 2n$), de tilldelade värdena i den nya hörnordningen.

Det garanteras att summan av $n$ över alla testfall inte överstiger $2 \cdot 10^5$.

Utdata

Första körningen. För varje testfall, skriv ut $n$ heltal $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2n$) på en rad. Heltalet $a_i$ är det värde som tilldelats hörn $i$.

Andra körningen. För varje testfall, skriv på första raden ut ett heltal $m$, antalet kanter. Var och en av de följande $m$ raderna måste innehålla två heltal $u$ och $v$ ($1 \le u, v \le n$, $u \ne v$), som beskriver en kant med de nya hörnnumren.

Skriv ut varje kant en gång, i valfri ordning. Vilken ändpunkt som helst kan komma först. Om $m = 0$, skriv endast ut $0$.

Exempel

Indata 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

Utdata 1

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

Indata 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

Utdata 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

Förklaring

I det första testfallet har skogen ett hörn och inga kanter. VegiCat tilldelar värdet $1$ till hörnet, och VegiDog skriver ut $0$.

I det sista testfallet är permutationen $p = [5, 3, 6, 4, 2, 9, 1, 8, 7, 10]$.

VegiCat tilldelar $a_7 = 16$. Eftersom $p_7 = 1$ får VegiDog $b_1 = 16$.

Den ursprungliga kanten $(3, 7)$ blir $(p_3, p_7) = (6, 1)$.

Den ursprungliga kanten $(4, 10)$ blir $(p_4, p_{10}) = (4, 10)$. Exemplet skriver ut denna kant som $(10, 4)$, vilket representerar samma oriktade kant.

Exemplet illustrerar formatet för indata och utdata. Dess utdata är korrekta för de grafer och permutationer som visas. Det garanteras dock inte att tilldelningarna i exemplet ingår i en strategi som fungerar för varje giltig skog och varje permutation.