Ce problème est un problème en deux passes (multi-pass).

VegiCat et VegiDog jouent à un jeu avec une forêt de $n$ sommets, numérotés de $1$ à $n$, et $m$ arêtes. Une forêt est un graphe non orienté sans cycle. Elle n'est pas nécessairement connexe.

Dans la première phase, VegiCat attribue un entier $a_u$ ($1 \le a_u \le 2n$) à chaque sommet $u$. Les valeurs peuvent se répéter.

Une fois que VegiCat a terminé d'attribuer les valeurs, les sommets sont renumérotés. Soit $p_1, p_2, \ldots, p_n$ une permutation de $1, 2, \ldots, n$, dans laquelle chaque entier de $1$ à $n$ apparaît exactement une fois. Pour chaque $u$, le sommet initialement numéroté $u$ porte désormais le numéro $p_u$.

Chaque arête $(u, v)$ devient $(p_u, p_v)$. Chaque sommet conserve la valeur qui lui a été attribuée. Soit $b_i$ la valeur au sommet $i$ après renumérotation. Alors $b_{p_u} = a_u$.

Dans la seconde phase, VegiDog reçoit uniquement $n$ et $b_1, b_2, \ldots, b_n$, sans la forêt initiale ni $p$. Il doit retrouver toutes les arêtes en utilisant les nouveaux numéros de sommets.

Concevez des stratégies pour les deux joueurs qui fonctionnent pour toute forêt valide et toute permutation $p$.

Entrée

Votre programme sera exécuté deux fois : d'abord dans le rôle de VegiCat, puis dans celui de VegiDog. Les cas de test apparaissent dans le même ordre lors des deux exécutions.

Première exécution. La première ligne contient la chaîne cat, indiquant que vous jouez VegiCat.

La deuxième ligne contient un entier $T$ ($1 \le T \le 10^4$), le nombre de cas de test. La description des cas de test suit.

La première ligne de chaque cas de test contient deux entiers $n$ et $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m < n$), le nombre de sommets et d'arêtes.

Chacune des $m$ lignes suivantes contient deux entiers $u$ et $v$ ($1 \le u, v \le n$, $u \ne v$), décrivant une arête non orientée entre les sommets $u$ et $v$.

Il est garanti que le graphe ne comporte ni cycle ni arête multiple.

Il est garanti que la somme de $n$ sur l'ensemble des cas de test ne dépasse pas $2 \cdot 10^5$.

Seconde exécution. La première ligne contient la chaîne dog, indiquant que vous jouez VegiDog.

La deuxième ligne contient un entier $T$ ($1 \le T \le 10^4$), le nombre de cas de test. La description des cas de test suit.

La première ligne de chaque cas de test contient un entier $n$ ($1 \le n \le 2 \cdot 10^5$), le nombre de sommets.

La deuxième ligne contient $n$ entiers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 2n$), les valeurs attribuées selon le nouvel ordre des sommets.

Il est garanti que la somme de $n$ sur l'ensemble des cas de test ne dépasse pas $2 \cdot 10^5$.

Sortie

Première exécution. Pour chaque cas de test, affichez $n$ entiers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2n$) sur une seule ligne. L'entier $a_i$ est la valeur attribuée au sommet $i$.

Seconde exécution. Pour chaque cas de test, affichez sur la première ligne un entier $m$, le nombre d'arêtes. Chacune des $m$ lignes suivantes doit contenir deux entiers $u$ et $v$ ($1 \le u, v \le n$, $u \ne v$), décrivant une arête à l'aide des nouveaux numéros de sommets.

Affichez chaque arête une seule fois, dans n'importe quel ordre. N'importe quelle extrémité peut apparaître en premier. Si $m = 0$, affichez uniquement $0$.

Exemples

Entrée 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

Sortie 1

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

Entrée 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

Sortie 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

Remarque

Dans le premier cas de test, la forêt possède un sommet et aucune arête. VegiCat attribue la valeur $1$ au sommet, et VegiDog affiche $0$.

Dans le dernier cas de test, la permutation est $p = [5, 3, 6, 4, 2, 9, 1, 8, 7, 10]$.

VegiCat attribue $a_7 = 16$. Comme $p_7 = 1$, VegiDog reçoit $b_1 = 16$.

L'arête initiale $(3, 7)$ devient $(p_3, p_7) = (6, 1)$.

L'arête initiale $(4, 10)$ devient $(p_4, p_{10}) = (4, 10)$. L'exemple affiche cette arête sous la forme $(10, 4)$, ce qui représente la même arête non orientée.

L'exemple illustre les formats d'entrée et de sortie. Ses sorties sont correctes pour les graphes et permutations présentés. Toutefois, rien ne garantit que les attributions de l'exemple fassent partie d'une stratégie fonctionnant pour toute forêt valide et toute permutation.