← 返回题目列表

Codeforces · 2029/D

D. 酷图

中文机器翻译题面 查看原题

给你一个无向图,其中有 $$$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$$$

请注意,在第一个操作之后,图形已经变得很酷,并且有两个额外的操作。由于图形在两次额外操作后仍然很酷,因此这是一个有效的答案。