CF788B Weird journey

小男孩 Igor 想成为一名旅行者。首先，他决定游遍他的祖国 Uzhlyandia 的所有城市。 众所周知，Uzhlyandia 有 $n$ 个城市，通过 $m$ 条双向道路连接。此外，国家中不存在两条连接同一对城市的道路，但可以有自环道路（即一条道路起点和终点在同一座城市）。Igor 想要提前规划他的旅行路线。他认为一条路径是好的，当且仅当该路径经过 $m-2$ 条道路各两次，另外 $2$ 条道路恰好各经过一次。好的路径可以从任意城市出发，也可以在任意城市结束。 现在他想知道 Uzhlyandia 中有多少条不同的好路径。如果两条路径经过恰好一次的道路集合不同，则认为这两条路径是不同的。请你帮 Igor 计算 Uzhlyandia 中好的路径的数量。

第一行包含两个整数 $n$ 和 $m$ $(1 \leq n,m \leq 10^{6})$，表示 Uzhlyandia 的城市数和道路数。 接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u,v \leq n$），表示存在一条连接城市 $u$ 和 $v$ 的道路。 保证输入中每条道路只出现一次，也就是说，任意一对城市之间最多只有一条道路直接相连，每座城市至多有一条自环道路。

输出唯一一个整数，表示在 Uzhlyandia 中好的路径数量。

在第一个样例测试中，好的路径有： - $2 \to 1 \to 3 \to 1 \to 4 \to 1 \to 5$， - $2 \to 1 \to 3 \to 1 \to 5 \to 1 \to 4$， - $2 \to 1 \to 4 \to 1 \to 5 \to 1 \to 3$， - $3 \to 1 \to 2 \to 1 \to 4 \to 1 \to 5$， - $3 \to 1 \to 2 \to 1 \to 5 \to 1 \to 4$， - $4 \to 1 \to 2 \to 1 \to 3 \to 1 \to 5$。 一些和上面相同的路径，因为恰好经过一次的道路集合相同，所以并不计作不同的路径： - $2 \to 1 \to 4 \to 1 \to 3 \to 1 \to 5$， - $2 \to 1 \to 5 \to 1 \to 3 \to 1 \to 4$， - $2 \to 1 \to 5 \to 1 \to 4 \to 1 \to 3$， - $3 \to 1 \to 4 \to 1 \to 2 \to 1 \to 5$， - $3 \to 1 \to 5 \to 1 \to 2 \to 1 \to 4$， - $4 \to 1 \to 3 \to 1 \to 2 \to 1 \to 5$， - 以及其它所有反向路径。 因此，答案为 $6$。 在第二个样例中，Igor 无法经过所有道路。 在第三个样例中，Igor 恰好每条道路经过一次。 由 ChatGPT 5 翻译