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 翻译