Se te proporciona un grafo no dirigido con $n$ vértices y $m$ aristas. Puedes realizar la siguiente operación como máximo $2 \cdot \max(n, m)$ veces:

• Elige tres vértices distintos $a$, $b$ y $c$, luego, para cada una de las aristas $(a, b)$, $(b, c)$ y $(c, a)$, haz lo siguiente:
  • Si la arista no existe, agrégala. Por el contrario, si existe, elimínala.

Un grafo se denomina cool si y solo si se cumple una de las siguientes condiciones:

• El grafo no tiene aristas, o
• El grafo es un árbol.

Debes hacer que el grafo sea cool realizando las operaciones anteriores. Ten en cuenta que puedes usar como máximo $2 \cdot \max(n, m)$ operaciones. Se puede demostrar que siempre existe al menos una solución.

Entrada

Cada prueba contiene múltiples casos de prueba. La primera línea de la entrada contiene un único 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$ ($3 \le n \le 10^5$, $0 \le m \le \min\left(\frac{n(n-1)}{2}, 2 \cdot 10^5\right)$) — el número de vértices y el número de aristas.

Luego siguen $m$ líneas, la $i$-ésima línea contiene dos enteros $u_i$ y $v_i$ ($1 \le u_i, v_i \le n$) — los dos nodos que conecta la $i$-ésima arista.

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

Se garantiza que no hay bucles ni aristas múltiples en el grafo dado.

Salida

Para cada caso de prueba, en la primera línea imprime un entero $k$ ($0 \le k \le 2 \cdot \max(n, m)$) — el número de operaciones.

Luego imprime $k$ líneas, la $i$-ésima línea conteniendo tres enteros distintos $a$, $b$ y $c$ ($1 \le a, b, c \le n$) — los tres enteros que eliges en la $i$-ésima operación.

Si hay múltiples soluciones, puedes imprimir cualquiera de ellas.

Ejemplos

Entrada 1

5
3 0
3 1
1 2
3 2
1 2
2 3
3 3
1 2
2 3
3 1
6 6
1 2
1 6
4 5
3 4
4 6
3 6

Salida 1

0
1
1 2 3
0
1
1 2 3
3
1 3 6
2 4 5
3 4 6

Nota

En el primer caso de prueba, el grafo ya es cool porque no hay aristas.

En el segundo caso de prueba, después de realizar la única operación, el grafo se convierte en un árbol, por lo que es cool.

En el tercer caso de prueba, el grafo ya es cool porque es un árbol.

En el cuarto caso de prueba, después de realizar la única operación, el grafo no tiene aristas, por lo que es cool.

En el quinto caso de prueba:

Figura 5.1. Grafo antes de la operación 1

Ten en cuenta que después de la primera operación, el grafo ya se ha vuelto cool, y hay dos operaciones adicionales. Como el grafo sigue siendo cool después de las dos operaciones adicionales, esta es una respuesta válida.