Þetta er tvíþætt (multi-pass) verkefni.

VegiCat og VegiDog spila leik með skógi sem hefur $n$ hnúta, númeraða frá $1$ til $n$, og $m$ leggi. Skógur er óstefndur leggjafjöldi án rása. Hann er ekki endilega samanhangandi.

Í fyrra þrepinu úthlutar VegiCat heiltölu $a_u$ ($1 \le a_u \le 2n$) á hvern hnút $u$. Gildin mega endurtaka sig.

Eftir að VegiCat hefur lokið við að úthluta gildunum eru hnútarnir endurnúmeraðir. Látum $p_1, p_2, \ldots, p_n$ vera umröðun á $1, 2, \ldots, n$, þar sem hver heiltala frá $1$ til $n$ kemur fyrir nákvæmlega einu sinni. Fyrir hvert $u$ fær hnúturinn sem upphaflega var númeraður $u$ nú númerið $p_u$.

Hver leggur $(u, v)$ verður að $(p_u, p_v)$. Hver hnútur heldur sínu úthlutaða gildi. Látum $b_i$ vera gildið á hnúti $i$ eftir endurnúmerunina. Þá er $b_{p_u} = a_u$.

Í seinna þrepinu fær VegiDog aðeins $n$ og $b_1, b_2, \ldots, b_n$, án upphaflega skógarins eða $p$. Hann verður að endurheimta alla leggi með því að nota nýju hnútanúmerin.

Hannaðu áætlanir fyrir báða leikmenn sem virka fyrir hvern gildan skóg og hverja umröðun $p$.

Inntak

Forritið þitt verður keyrt tvisvar: fyrst sem VegiCat, síðan sem VegiDog. Prófunartilvikin birtast í sömu röð í báðum keyrslum.

Fyrri keyrsla. Fyrsta línan inniheldur strenginn cat, sem gefur til kynna að þú leikir VegiCat.

Önnur línan inniheldur heiltölu $T$ ($1 \le T \le 10^4$), fjölda prófunartilvika. Lýsing á prófunartilvikunum fylgir.

Fyrsta línan í hverju prófunartilviki inniheldur tvær heiltölur $n$ og $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m < n$), fjölda hnúta og leggja.

Hver af næstu $m$ línum inniheldur tvær heiltölur $u$ og $v$ ($1 \le u, v \le n$, $u \ne v$), sem lýsa óstefndum legg á milli hnúta $u$ og $v$.

Það er tryggt að netið innihaldi hvorki rásir né margfalda leggi.

Það er tryggt að summa $n$ yfir öll prófunartilvik fari ekki yfir $2 \cdot 10^5$.

Seinni keyrsla. Fyrsta línan inniheldur strenginn dog, sem gefur til kynna að þú leikir VegiDog.

Önnur línan inniheldur heiltölu $T$ ($1 \le T \le 10^4$), fjölda prófunartilvika. Lýsing á prófunartilvikunum fylgir.

Fyrsta línan í hverju prófunartilviki inniheldur heiltölu $n$ ($1 \le n \le 2 \cdot 10^5$), fjölda hnúta.

Önnur línan inniheldur $n$ heiltölur $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 2n$), úthlutuðu gildin í nýju hnútaröðinni.

Það er tryggt að summa $n$ yfir öll prófunartilvik fari ekki yfir $2 \cdot 10^5$.

Úttak

Fyrri keyrsla. Fyrir hvert prófunartilvik skal prenta út $n$ heiltölur $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2n$) á einni línu. Heiltalan $a_i$ er gildið sem úthlutað var hnúti $i$.

Seinni keyrsla. Fyrir hvert prófunartilvik skal prenta út heiltölu $m$ á fyrstu línu, fjölda leggja. Hver af næstu $m$ línum verður að innihalda tvær heiltölur $u$ og $v$ ($1 \le u, v \le n$, $u \ne v$), sem lýsa legg með nýju hnútanúmerunum.

Prentaðu hvern legg einu sinni, í hvaða röð sem er. Hvor endapunkturinn sem er má koma á undan. Ef $m = 0$ skal aðeins prenta út $0$.

Dæmi

Inntak 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

Úttak 1

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

Inntak 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

Úttak 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

Athugasemd

Í fyrsta prófunartilvikinu hefur skógurinn einn hnút og enga leggi. VegiCat úthlutar gildinu $1$ á hnútinn, og VegiDog prentar út $0$.

Í síðasta prófunartilvikinu er umröðunin $p = [5, 3, 6, 4, 2, 9, 1, 8, 7, 10]$.

VegiCat úthlutar $a_7 = 16$. Þar sem $p_7 = 1$, fær VegiDog $b_1 = 16$.

Upphaflegi leggurinn $(3, 7)$ verður að $(p_3, p_7) = (6, 1)$.

Upphaflegi leggurinn $(4, 10)$ verður að $(p_4, p_{10}) = (4, 10)$. Dæmið prentar þennan legg út sem $(10, 4)$, sem táknar sama óstefnda legginn.

Dæmið sýnir snið inntaks og úttaks. Úttök þess eru rétt fyrir netin og umraðanirnar sem sýndar eru. Hins vegar er ekki tryggt að úthlutanirnar í dæminu séu hluti af áætlun sem virkar fyrir hvern gildan skóg og hverja umröðun.