题目描述

设 $G = (V, E)$ 是一个有 $N$ 个顶点和 $M$ 条边的简单无向图，其中 $V = \{1, \dots, N\}$。若 $\{(u,v), (v,w)\} \subseteq E$ 且 $u \neq w$，则称三元组 $\langle u, v, w \rangle$ 为 $G$ 中的 回旋镖；换句话说，一个回旋镖由两条共享一个公共顶点的边组成。

给定 $G$，你的任务是在 $G$ 中找出尽可能多的不相交回旋镖。一个集合 $S$ 包含不相交的回旋镖，当且仅当 $G$ 中的每条边在 $S$ 中至多出现一次（即最多属于一个回旋镖）。你可以输出任意一组有效的不相交回旋镖，但回旋镖的数量必须最大。

例如，考虑一个图 $G = (V, E)$，其中 $N = 5$ 个顶点，$M = 7$ 条边，$E = \{(1,2), (1,4), (2,3), (2,4), (2,5), (3,4), (3,5)\}$。

:::align{center} :::

在此示例图中，不相交回旋镖的最大数量为 $3$。包含 $3$ 个不相交回旋镖的一个示例集合为 $\{\langle 4,1,2 \rangle, \langle 4,3,2 \rangle, \langle 2,5,3 \rangle\}$；在此示例中，不存在包含超过 $3$ 个不相交回旋镖的集合。

输入格式

输入的第一行包含两个整数：$N$ 和 $M$（$1 \leq N, M \leq 100000$），分别表示 $G$ 中的顶点数和边数。接下来的 $M$ 行，每行包含两个整数：$u_i$ 和 $v_i$（$1 \leq u_i < v_i \leq N$），表示 $G$ 中的一条边 $(u_i, v_i)$。你可以假定每条边在给定列表中至多出现一次。

输出格式

输出的第一行包含一个整数 $K$，表示 $G$ 中不相交回旋镖的最大数量。接下来的 $K$ 行，每行包含三个整数：$u$、$v$ 和 $w$（每个整数之间用一个空格分隔），表示一个回旋镖 $\langle u,v,w \rangle$。输出中的所有回旋镖应互不相交。如果存在多个有效解，你可以输出其中任意一个。

5 7
1 2
1 4
2 3
2 4
2 5
3 4
3 5

3
4 1 2
4 3 2
2 5 3

4 6
1 2
1 3
1 4
2 3
2 4
3 4

3
1 2 3
1 3 4
1 4 2

3 3
1 2
1 3
2 3

1
2 1 3

提示

翻译由 DeepSeek V3.2 完成