On vous donne un graphe non orienté avec $n$ sommets et $m$ arêtes. Vous pouvez effectuer l'opération suivante au plus $2 \cdot \max(n, m)$ fois :

• Choisir trois sommets distincts $a$, $b$ et $c$, puis pour chacune des arêtes $(a, b)$, $(b, c)$ et $(c, a)$, faire ce qui suit :
  • Si l'arête n'existe pas, ajoutez-la. Au contraire, si elle existe, supprimez-la.

Un graphe est dit cool si et seulement si l'une des conditions suivantes est vraie :

• Le graphe n'a aucune arête, ou
• Le graphe est un arbre.

Vous devez rendre le graphe cool en effectuant les opérations ci-dessus. Notez que vous pouvez utiliser au plus $2 \cdot \max(n, m)$ opérations. Il peut être démontré qu'il existe toujours au moins une solution.

Entrée

Chaque test contient plusieurs cas de test. La première ligne de l'entrée contient un entier unique $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$ ($3 \le n \le 10^5$, $0 \le m \le \min\left(\frac{n(n-1)}{2}, 2 \cdot 10^5\right)$) — le nombre de sommets et le nombre d'arêtes.

Ensuite, $m$ lignes suivent, la $i$-ième ligne contient deux entiers $u_i$ et $v_i$ ($1 \le u_i, v_i \le n$) — les deux nœuds que la $i$-ième arête relie.

Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $10^5$, et la somme de $m$ sur tous les cas de test ne dépasse pas $2 \cdot 10^5$. Il est garanti qu'il n'y a pas de boucles ou d'arêtes multiples dans le graphe donné.

Sortie

Pour chaque cas de test, affichez sur la première ligne un entier $k$ ($0 \le k \le 2 \cdot \max(n, m)$) — le nombre d'opérations. Ensuite, affichez $k$ lignes, la $i$-ième ligne contenant trois entiers distincts $a$, $b$ et $c$ ($1 \le a, b, c \le n$) — les trois entiers que vous choisissez lors de la $i$-ième opération.

S'il existe plusieurs solutions, vous pouvez en afficher n'importe laquelle.

Exemples

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

Sortie 1

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

Remarque

Dans le premier cas de test, le graphe est déjà cool car il n'y a pas d'arêtes. Dans le deuxième cas de test, après avoir effectué l'unique opération, le graphe devient un arbre, il est donc cool. Dans le troisième cas de test, le graphe est déjà cool car c'est un arbre. Dans le quatrième cas de test, après avoir effectué l'unique opération, le graphe n'a plus d'arêtes, il est donc cool. Dans le cinquième cas de test :

Figure 1. Opérations sur le graphe

Notez qu'après la première opération, le graphe est déjà devenu cool, et il y a deux opérations supplémentaires. Comme le graphe est toujours cool après les deux opérations supplémentaires, il s'agit d'une réponse valide.