Dany jest graf nieskierowany o $n$ wierzchołkach i $m$ krawędziach. Możesz wykonać następującą operację co najwyżej $2 \cdot \max(n, m)$ razy:

• Wybierz trzy różne wierzchołki $a$, $b$ oraz $c$, a następnie dla każdej z krawędzi $(a, b)$, $(b, c)$ oraz $(c, a)$ wykonaj następujące czynności:
  • Jeśli krawędź nie istnieje, dodaj ją. W przeciwnym razie, jeśli istnieje, usuń ją.

Graf nazywamy cool wtedy i tylko wtedy, gdy spełniony jest jeden z poniższych warunków:

• Graf nie posiada krawędzi, lub
• Graf jest drzewem.

Musisz sprawić, aby graf stał się cool, wykonując powyższe operacje. Zauważ, że możesz wykonać co najwyżej $2 \cdot \max(n, m)$ operacji. Można wykazać, że zawsze istnieje co najmniej jedno rozwiązanie.

Wejście

Każdy test zawiera wiele przypadków testowych. Pierwsza linia wejścia zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 10^4$) — liczbę przypadków testowych. Następuje opis przypadków testowych.

Pierwsza linia każdego przypadku testowego zawiera dwie liczby całkowite $n$ oraz $m$ ($3 \le n \le 10^5$, $0 \le m \le \min\left(\frac{n(n-1)}{2}, 2 \cdot 10^5\right)$) — liczbę wierzchołków oraz liczbę krawędzi.

Następnie następuje $m$ linii, z których $i$-ta zawiera dwie liczby całkowite $u_i$ oraz $v_i$ ($1 \le u_i, v_i \le n$) — dwa wierzchołki połączone $i$-tą krawędzią.

Gwarantuje się, że suma $n$ we wszystkich przypadkach testowych nie przekracza $10^5$, a suma $m$ we wszystkich przypadkach testowych nie przekracza $2 \cdot 10^5$.

Gwarantuje się, że w podanym grafie nie ma pętli własnych ani krawędzi wielokrotnych.

Wyjście

Dla każdego przypadku testowego w pierwszej linii wypisz liczbę całkowitą $k$ ($0 \le k \le 2 \cdot \max(n, m)$) — liczbę operacji.

Następnie wypisz $k$ linii, z których $i$-ta zawiera trzy różne liczby całkowite $a$, $b$ oraz $c$ ($1 \le a, b, c \le n$) — trzy wierzchołki wybrane w $i$-tej operacji.

Jeśli istnieje wiele rozwiązań, możesz wypisać dowolne z nich.

Przykład

Wejście 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

Wyjście 1

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

Uwagi

W pierwszym przypadku testowym graf jest już cool, ponieważ nie posiada krawędzi.

W drugim przypadku testowym, po wykonaniu jedynej operacji, graf staje się drzewem, więc jest cool.

W trzecim przypadku testowym graf jest już cool, ponieważ jest drzewem.

W czwartym przypadku testowym, po wykonaniu jedynej operacji, graf nie posiada krawędzi, więc jest cool.

W piątym przypadku testowym:

Graf przed operacją 1

Zauważ, że po pierwszej operacji graf stał się już cool, a wykonano dwie dodatkowe operacje. Ponieważ graf nadal jest cool po tych dwóch dodatkowych operacjach, jest to poprawne rozwiązanie.