Este es un problema de múltiples pasadas (multi-pass).

VegiCat y VegiDog juegan con un bosque de $n$ vértices, numerados del $1$ al $n$, y $m$ aristas. Un bosque es un grafo no dirigido sin ciclos. No es necesariamente conexo.

En la primera etapa, VegiCat asigna un entero $a_u$ ($1 \le a_u \le 2n$) a cada vértice $u$. Los valores pueden repetirse.

Después de que VegiCat termina de asignar los valores, los vértices se vuelven a numerar. Sea $p_1, p_2, \ldots, p_n$ una permutación de $1, 2, \ldots, n$, en la cual cada entero del $1$ al $n$ aparece exactamente una vez. Para cada $u$, el vértice originalmente numerado $u$ ahora pasa a tener el número $p_u$.

Cada arista $(u, v)$ se convierte en $(p_u, p_v)$. Cada vértice conserva su valor asignado. Sea $b_i$ el valor en el vértice $i$ tras la renumeración. Entonces $b_{p_u} = a_u$.

En la segunda etapa, VegiDog recibe únicamente $n$ y $b_1, b_2, \ldots, b_n$, sin el bosque original ni $p$. Debe recuperar todas las aristas utilizando los nuevos números de los vértices.

Diseña estrategias para ambos jugadores que funcionen para cualquier bosque válido y cualquier permutación $p$.

Entrada

Tu programa se ejecutará dos veces: primero como VegiCat y luego como VegiDog. Los casos de prueba aparecen en el mismo orden en ambas ejecuciones.

Primera ejecución. La primera línea contiene la cadena cat, indicando que juegas como VegiCat.

La segunda línea contiene un entero $T$ ($1 \le T \le 10^4$), el número de casos de prueba. A continuación sigue la descripción de los casos de prueba.

La primera línea de cada caso de prueba contiene dos enteros $n$ y $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m < n$), el número de vértices y aristas.

Cada una de las siguientes $m$ líneas contiene dos enteros $u$ y $v$ ($1 \le u, v \le n$, $u \ne v$), que describen una arista no dirigida entre los vértices $u$ y $v$.

Se garantiza que el grafo no tiene ciclos ni aristas múltiples.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $2 \cdot 10^5$.

Segunda ejecución. La primera línea contiene la cadena dog, indicando que juegas como VegiDog.

La segunda línea contiene un entero $T$ ($1 \le T \le 10^4$), el número de casos de prueba. A continuación sigue la descripción de los casos de prueba.

La primera línea de cada caso de prueba contiene un entero $n$ ($1 \le n \le 2 \cdot 10^5$), el número de vértices.

La segunda línea contiene $n$ enteros $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 2n$), los valores asignados en el nuevo orden de vértices.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $2 \cdot 10^5$.

Salida

Primera ejecución. Para cada caso de prueba, imprime $n$ enteros $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2n$) en una línea. El entero $a_i$ es el valor asignado al vértice $i$.

Segunda ejecución. Para cada caso de prueba, imprime en la primera línea un entero $m$, el número de aristas. Cada una de las siguientes $m$ líneas debe contener dos enteros $u$ y $v$ ($1 \le u, v \le n$, $u \ne v$), describiendo una arista mediante los nuevos números de vértices.

Imprime cada arista una vez, en cualquier orden. Cualquiera de los extremos puede ir primero. Si $m = 0$, imprime únicamente $0$.

Ejemplos

Entrada 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

Salida 1

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

Entrada 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

Salida 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

Nota

En el primer caso de prueba, el bosque tiene un vértice y ninguna arista. VegiCat asigna el valor $1$ al vértice y VegiDog imprime $0$.

En el último caso de prueba, la permutación es $p = [5, 3, 6, 4, 2, 9, 1, 8, 7, 10]$.

VegiCat asigna $a_7 = 16$. Como $p_7 = 1$, VegiDog recibe $b_1 = 16$.

La arista original $(3, 7)$ se convierte en $(p_3, p_7) = (6, 1)$.

La arista original $(4, 10)$ se convierte en $(p_4, p_{10}) = (4, 10)$. El ejemplo imprime esta arista como $(10, 4)$, lo que representa la misma arista no dirigida.

El ejemplo ilustra los formatos de entrada y salida. Sus salidas son correctas para los grafos y permutaciones mostrados. Sin embargo, no se garantiza que las asignaciones del ejemplo formen parte de una estrategia que funcione para todo bosque válido y toda permutación.