CF858F Wizard's Tour

所有 Berland 的居民都在期待巫师乘坐他的蓝色直升机在 Berland 各个城市进行一场前所未有的巡回演出！ 众所周知，Berland 有 $n$ 个城市，其中一些城市之间通过双向公路相连。任意两座城市之间最多只有一条公路。并不保证整个公路网络是连通的，也就是说，有些城市之间可能无法直接或间接到达。 巡演将包含若干次表演，每次表演包括以下过程： - 巫师会在某个城市 $x$ 从直升机上下来； - 他会在城市 $x$ 举办一场演出并免费观看电影； - 然后他会通过一条公路前往相邻的城市 $y$； - 他会在城市 $y$ 举办一场演出并免费观看电影； - 接着他会通过一条公路前往与 $y$ 相邻的城市 $z$； - 他会在城市 $z$ 举办一场演出并免费观看电影； - 最后他会在城市 $z$ 登上直升机飞离。 已知巫师不喜欢反复使用公路，所以每条公路最多只能被使用一次（无论方向如何）。换句话说，对于连接 $a$ 和 $b$ 的公路，只能从 $a$ 到 $b$ 或者从 $b$ 到 $a$ 走一次，或者压根不用。 巫师希望在不违反上述规则的前提下，规划出尽可能多的表演次数。请你帮助巫师！ 注意，巫师可以多次访问同一座城市，限制只在于公路的使用次数。

第一行包含两个整数 $n$、$m$（$1 \leq n \leq 2 \cdot 10^{5}$，$0 \leq m \leq 2 \cdot 10^{5}$），分别表示 Berland 的城市数量和公路数量。 接下来 $m$ 行，每行两个整数 $a_{i}, b_{i}$（$1 \leq a_{i}, b_{i} \leq n$，$a_{i} \ne b_{i}$），表示第 $i$ 条公路连接了编号为 $a_{i}$ 和 $b_{i}$ 的两座城市。保证没有两条公路连接同一对城市。每条公路都是双向的。城市编号从 $1$ 到 $n$。 Berland 的公路网络可能不是连通的。

输出第一行为整数 $w$，表示最多能规划多少次表演。接下来的 $w$ 行，每行三个整数 $x, y, z$，表示巫师每次表演访问的三座城市编号，顺序分别为下直升机、第一站和第二站。

由 ChatGPT 5 翻译