给你一个无向图,其中有 $$$n$$$ 个顶点和 $$$m$$$ 个边。
您最多可以执行以下操作 $$$2\cdot \max(n,m)$$$ 次:
- 选择三个不同的顶点 $$$a$$$、$$$b$$$ 和 $$$c$$$,然后对于每条边 $$$(a,b)$$$、$$$(b,c)$$$ 和 $$$(c,a)$$$,执行以下操作: 如果边不存在,则添加它。反之,如果存在,则将其删除。
当且仅当满足以下条件之一时,图才称为冷图:
- 该图没有边,或者
- 该图是一棵树。
通过执行上述操作,您必须使图表变酷。请注意,您最多可以使用 $$$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$$$
请注意,在第一个操作之后,图形已经变得很酷,并且有两个额外的操作。由于图形在两次额外操作后仍然很酷,因此这是一个有效的答案。