Дан неориентированный граф с $n$ вершинами и $m$ ребрами. Вы можете выполнить следующую операцию не более $2 \cdot \max(n, m)$ раз:

• Выберите три различные вершины $a$, $b$ и $c$, затем для каждого из ребер $(a, b)$, $(b, c)$ и $(c, a)$ выполните следующее:
  • Если ребро не существует, добавьте его. Напротив, если оно существует, удалите его.

Граф называется крутым (cool), если выполняется одно из следующих условий: В графе нет ребер, или Граф является деревом.

Вам необходимо сделать граф крутым, выполняя вышеуказанные операции. Обратите внимание, что вы можете использовать не более $2 \cdot \max(n, m)$ операций. Можно показать, что решение всегда существует.

Входные данные

Каждый тест содержит несколько наборов входных данных. В первой строке входных данных содержится единственное целое число $t$ ($1 \le t \le 10^4$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит два целых числа $n$ и $m$ ($3 \le n \le 10^5$, $0 \le m \le \min\left(\frac{n(n-1)}{2}, 2 \cdot 10^5\right)$) — количество вершин и количество ребер.

Затем следуют $m$ строк, $i$-я строка содержит два целых числа $u_i$ и $v_i$ ($1 \le u_i, v_i \le n$) — два узла, которые соединяет $i$-е ребро.

Гарантируется, что сумма $n$ по всем наборам входных данных не превышает $10^5$, а сумма $m$ по всем наборам входных данных не превышает $2 \cdot 10^5$.

Гарантируется, что в заданном графе нет петель и кратных ребер.

Выходные данные

Для каждого набора входных данных в первой строке выведите целое число $k$ ($0 \le k \le 2 \cdot \max(n, m)$) — количество операций. Затем выведите $k$ строк, $i$-я строка должна содержать три различных целых числа $a$, $b$ и $c$ ($1 \le a, b, c \le n$) — три вершины, которые вы выбираете в $i$-й операции.

Если существует несколько решений, вы можете вывести любое из них.

Примеры

Входные данные 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

Выходные данные 1

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

Примечание

В первом наборе входных данных граф уже является крутым, так как в нем нет ребер. Во втором наборе входных данных после выполнения единственной операции граф становится деревом, поэтому он является крутым. В третьем наборе входных данных граф уже является крутым, так как он является деревом. В четвертом наборе входных данных после выполнения единственной операции в графе нет ребер, поэтому он является крутым. В пятом наборе входных данных:

Операция 1: Граф до и после

Операция 2: Граф до и после

Операция 3: Граф до и после

Обратите внимание, что после первой операции граф уже стал крутым, и есть две дополнительные операции. Поскольку граф остается крутым после двух дополнительных операций, это допустимый ответ.