给定一个包含 $n$ 个顶点和 $m$ 条边的无向图。 你可以执行以下操作，最多执行 $2 \cdot \max(n, m)$ 次：

• 选择三个不同的顶点 $a, b$ 和 $c$，然后对于边 $(a, b), (b, c)$ 和 $(c, a)$ 中的每一条，执行以下操作：
  • 如果该边不存在，则添加它。反之，如果它存在，则将其删除。

当且仅当满足以下条件之一时，称该图为 cool：

• 该图没有边，或者
• 该图是一棵树。

你需要通过执行上述操作使图变得 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(\frac{n(n-1)}{2}, 2 \cdot 10^5)$) —— 顶点数和边数。 接下来 $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

说明

在第一个测试用例中，图已经是 cool 的，因为没有边。 在第二个测试用例中，执行唯一的操作后，图变成了一棵树，因此它是 cool 的。 在第三个测试用例中，图已经是 cool 的，因为它是一棵树。 在第四个测试用例中，执行唯一的操作后，图没有边，因此它是 cool 的。 在第五个测试用例中：

操作 1

注意，在第一次操作后，图已经变得 cool，并且还有两次额外的操作。由于在两次额外操作后图仍然是 cool 的，这是一个有效的答案。