$n$ 個の頂点と $m$ 個の辺を持つ無向グラフが与えられます。 あなたは、以下の操作を最大で $2 \cdot \max(n, m)$ 回まで行うことができます。

• 相異なる3つの頂点 $a, b, c$ を選び、辺 $(a, b), (b, c), (c, a)$ のそれぞれに対して以下を行う。
  • その辺が存在しない場合は追加し、存在する場合には削除する。

グラフは、以下のいずれかの条件を満たすとき「クール (cool)」であると呼ばれます。

• グラフに辺が存在しない。
• グラフが木である。

上記の操作を行い、グラフをクールにしてください。なお、操作回数は最大で $2 \cdot \max(n, m)$ 回まで使用可能です。 少なくとも1つの解が常に存在することが示せます。

入力

各テストケースは複数のテストケースを含みます。入力の最初の行には、テストケースの数 $t$ ($1 \le t \le 10^4$) が含まれます。各テストケースの記述は以下の通りです。

各テストケースの最初の行には、2つの整数 $n$ と $m$ ($3 \le n \le 10^5, 0 \le m \le \min(\frac{n(n-1)}{2}, 2 \cdot 10^5)$) が含まれます。これは頂点の数と辺の数です。

続く $m$ 行には、それぞれ2つの整数 $u_i$ と $v_i$ ($1 \le u_i, v_i \le n$) が含まれ、これは $i$ 番目の辺が接続する2つのノードを表します。

すべてのテストケースにおける $n$ の総和は $10^5$ を超えず、$m$ の総和は $2 \cdot 10^5$ を超えないことが保証されます。 与えられたグラフに自己ループや多重辺は存在しないことが保証されます。

出力

各テストケースについて、最初の行に操作回数 $k$ ($0 \le k \le 2 \cdot \max(n, m)$) を出力してください。 続く $k$ 行には、各操作で選ぶ3つの相異なる整数 $a, b, c$ ($1 \le a, b, c \le n$) を出力してください。

複数の解が存在する場合、どれを出力しても構いません。

入出力例

入力 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番目のテストケースでは、グラフはすでに木であるためクールです。 4番目のテストケースでは、唯一の操作を行った後、グラフには辺が存在しなくなるためクールです。 5番目のテストケースについて：

操作 1: 操作前のグラフ

操作 1: 操作後のグラフ

操作 2: 操作前のグラフ

操作 2: 操作後のグラフ

操作 3: 操作前のグラフ

操作 3: 操作後のグラフ

最初の操作の後でグラフはすでにクールになっており、余分な操作が2回行われていることに注意してください。グラフは2回の余分な操作の後でもクールな状態であるため、これは有効な回答です。