CF2029D Cool Graph

给定一个无向图，包含 $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\left(\frac{n(n-1)}{2},2\cdot 10^5\right)$）——表示顶点数和边数。 接下来 $m$ 行，每行包含两个整数 $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$ 行，每行包含三个不同的整数 $a$、$b$、$c$（$1\le a,b,c\le n$）——表示你在第 $i$ 次操作中选择的三个顶点。 如果有多种方案，输出任意一种均可。

在第一个测试用例中，图已经是 cool 的，因为没有边。 在第二个测试用例中，经过唯一的一次操作后，图变成了一棵树，因此是 cool 的。 在第三个测试用例中，图已经是一棵树，因此是 cool 的。 在第四个测试用例中，经过唯一的一次操作后，图中没有边，因此是 cool 的。 在第五个测试用例中： 操作编号 操作前的图 操作后的图 $1$  $2$  $3$ 注意，在第一次操作后，图已经变成了 cool 的，后面两次操作是多余的。只要最终图仍然是 cool 的，这也是一个合法答案。 由 ChatGPT 4.1 翻译