Bajtazar es un alquimista conocido que ha dejado temporalmente de lado sus intentos de crear la piedra filosofal para dedicarse a la transmutación de materiales. Más precisamente, Bajtazar desea transformar una molécula en otra. La molécula que posee Bajtazar consta de $n$ átomos de bajtonio, numerados del 1 al $n$. Entre algunos pares de átomos pueden existir enlaces, donde entre cada par de átomos puede haber como máximo un enlace. La molécula de Bajtazar forma un todo conectado: desde cada átomo se puede llegar a cualquier otro pasando por uno o más enlaces.

Bajtazar posee una descripción de los enlaces para la molécula de $n$ átomos que desea obtener; para cada par de átomos, sabe si desea que finalmente estén conectados por un enlace o no. La molécula objetivo cumple las mismas condiciones: forma un todo conectado y cada par de átomos está conectado por como máximo un enlace. Desafortunadamente, la molécula de Bajtazar puede diferir de la molécula objetivo. Para remediar esto, puede utilizar sus habilidades alquímicas. En cualquier momento, puede realizar una de las dos operaciones posibles:

• Bajtazar puede elegir dos átomos diferentes $a$ y $b$ que no estén conectados por un enlace y crear un enlace entre ellos. Debido a la gran inestabilidad del bajtonio, solo puede hacerlo si existe un átomo $c$ (distinto de $a$ y $b$) conectado actualmente por enlaces tanto a $a$ como a $b$.
• Bajtazar puede elegir dos átomos diferentes $a$ y $b$ conectados por un enlace y eliminar el enlace que los une. Por razones similares, solo puede hacerlo si existe un átomo $c$ (distinto de $a$ y $b$) conectado actualmente por enlaces tanto a $a$ como a $b$.

Bajtazar no quiere pasar demasiado tiempo en la transformación. Escribe un programa que le ayude a transformar su molécula en la objetivo en un máximo de 200 000 movimientos.

Entrada

La primera línea de la entrada contiene un número entero $n$ ($2 \le n \le 30\,000$), que representa el número de átomos en la molécula que posee Bajtazar, así como en la molécula objetivo.

La segunda línea de la entrada contiene un número entero $m_s$ ($n-1 \le m_s \le 50\,000$), que representa el número de enlaces en la molécula que posee Bajtazar.

En las siguientes $m_s$ líneas de la entrada hay dos números enteros. Los números en la $i$-ésima de estas líneas, $a_i$ y $b_i$ ($1 \le a_i, b_i \le n; a_i \neq b_i$), representan los números de los átomos conectados por un enlace. Se garantiza que la molécula de Bajtazar forma un todo conectado y que cada par de átomos puede estar conectado por como máximo un enlace.

La siguiente línea de la entrada contiene un número entero $m_d$ ($n-1 \le m_d \le 50\,000$), que representa el número de enlaces en la molécula objetivo.

En las siguientes $m_d$ líneas se encuentra la descripción de dichos enlaces, en un formato idéntico al formato de la molécula inicial.

Salida

En la primera línea de la salida debe aparecer el número de movimientos $r$ que deseas realizar. Debe cumplirse que $0 \le r \le 200\,000$.

En cada una de las siguientes $r$ líneas deben aparecer las descripciones de los movimientos sucesivos. Si en el $i$-ésimo movimiento deseas conectar los átomos $x_i$ y $y_i$ con un enlace, la $i$-ésima línea debe comenzar con el signo '+', y después de un espacio simple deben aparecer los números $x_i$ y $y_i$, también separados por un espacio simple. Si en su lugar deseas eliminar el enlace que conecta los átomos $x_i$ y $y_i$, la línea debe comenzar con el signo '-', y luego, de manera análoga, debe contener los números $x_i$ y $y_i$.

La secuencia de movimientos que escribas debe cumplir con las condiciones dadas en el enunciado: en el momento de elegir los átomos $x_i$ y $y_i$, debe existir otro átomo conectado a ambos. Después de realizar la secuencia de movimientos, la molécula final debe ser idéntica a la objetivo: para cada par de átomos $i, j$ ($1 \le i < j \le n$), los átomos numerados $i$ y $j$ deben estar conectados por un enlace en la molécula final si y solo si esos átomos están conectados por un enlace en la molécula objetivo.

Ten en cuenta que no necesitas minimizar el número de movimientos; basta con que realices como máximo 200 000. Se puede demostrar que la transformación siempre se puede realizar ejecutando como máximo 200 000 movimientos.

Ejemplos

Entrada 1

4
3
1 2
3 4
3 2
4
1 4
1 2
2 3
3 4

Salida 1

3
+ 1 3
+ 1 4
- 3 1

Nota

Explicación del ejemplo: Observa que Bajtazar no pudo conectar directamente el primer átomo con el cuarto, ya que en ese momento no existía ningún átomo conectado a ambos. Al crear un enlace temporal entre el primer y el tercer átomo, hizo que el tercer átomo fuera ese átomo intermedio.