Dette er et totrinnsproblem (multi-pass).

VegiCat og VegiDog spiller et spill med en skog med $n$ noder, nummerert fra $1$ til $n$, og $m$ kanter. En skog er en urettet graf uten sykler. Den er ikke nødvendigvis sammenhengende.

I det første trinnet tildeler VegiCat et heltall $a_u$ ($1 \le a_u \le 2n$) til hver node $u$. Verdiene kan gjentas.

Etter at VegiCat er ferdig med å tildele verdiene, blir nodene omnummerert. La $p_1, p_2, \ldots, p_n$ være en permutasjon av $1, 2, \ldots, n$, der hvert heltall fra $1$ til $n$ forekommer nøyaktig én gang. For hver $u$ får noden som opprinnelig hadde nummer $u$ nå nummeret $p_u$.

Hver kant $(u, v)$ blir $(p_u, p_v)$. Hver node beholder sin tildelte verdi. La $b_i$ være verdien i node $i$ etter omnummereringen. Da er $b_{p_u} = a_u$.

I det andre trinnet mottar VegiDog kun $n$ og $b_1, b_2, \ldots, b_n$, uten den opprinnelige skogen eller $p$. Han må gjenopprette alle kanter ved å bruke de nye nodenumrene.

Utform strategier for begge spillerne som fungerer for enhver gyldig skog og enhver permutasjon $p$.

Inndata

Programmet ditt vil bli kjørt to ganger: først som VegiCat, deretter som VegiDog. Testtilfellene kommer i samme rekkefølge i begge kjøringene.

Første kjøring. Den første linjen inneholder strengen cat, som angir at du spiller VegiCat.

Den andre linjen inneholder et heltall $T$ ($1 \le T \le 10^4$), antallet testtilfeller. Beskrivelsen av testtilfellene følger.

Den første linjen i hvert testtilfelle inneholder to heltall $n$ og $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m < n$), antallet noder og kanter.

Hver av de neste $m$ linjene inneholder to heltall $u$ og $v$ ($1 \le u, v \le n$, $u \ne v$), som beskriver en urettet kant mellom nodene $u$ og $v$.

Det garanteres at grafen ikke har sykler eller multippelkanter.

Det garanteres at summen av $n$ over alle testtilfeller ikke overstiger $2 \cdot 10^5$.

Andre kjøring. Den første linjen inneholder strengen dog, som angir at du spiller VegiDog.

Den andre linjen inneholder et heltall $T$ ($1 \le T \le 10^4$), antallet testtilfeller. Beskrivelsen av testtilfellene følger.

Den første linjen i hvert testtilfelle inneholder et heltall $n$ ($1 \le n \le 2 \cdot 10^5$), antallet noder.

Den andre linjen inneholder $n$ heltall $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 2n$), de tildelte verdiene i den nye noderekkefølgen.

Det garanteres at summen av $n$ over alle testtilfeller ikke overstiger $2 \cdot 10^5$.

Utdata

Første kjøring. For hvert testtilfelle skal du skrive ut $n$ heltall $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2n$) på én linje. Heltallet $a_i$ er verdien som er tildelt node $i$.

Andre kjøring. For hvert testtilfelle skal du på første linje skrive ut et heltall $m$, antallet kanter. Hver av de neste $m$ linjene må inneholde to heltall $u$ og $v$ ($1 \le u, v \le n$, $u \ne v$), som beskriver en kant ved hjelp av de nye nodenumrene.

Skriv ut hver kant én gang, i hvilken som helst rekkefølge. Hvilket som helst endepunkt kan komme først. Hvis $m = 0$, skriver du kun ut $0$.

Eksempler

Inndata 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

Inndata 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

Forklaring

I det første testtilfellet har skogen én node og ingen kanter. VegiCat tildeler verdien $1$ til noden, og VegiDog skriver ut $0$.

I det siste testtilfellet er permutasjonen $p = [5, 3, 6, 4, 2, 9, 1, 8, 7, 10]$.

VegiCat tildeler $a_7 = 16$. Siden $p_7 = 1$, mottar VegiDog $b_1 = 16$.

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

Den opprinnelige kanten $(4, 10)$ blir $(p_4, p_{10}) = (4, 10)$. Eksempelet skriver ut denne kanten som $(10, 4)$, som representerer den samme urettede kanten.

Eksempelet illustrerer formatene for inndata og utdata. Utdataene er korrekte for grafene og permutasjonene som vises. Det er imidlertid ikke garantert at tildelingene i eksempelet er en del av en strategi som fungerer for enhver gyldig skog og enhver permutasjon.