从国家集训队的论文集里看到的题，既然没人写题解那我也就参考一下论文集里的话写一篇题解了。

这里把陈通写的论文放上来供大家看一下吧。

[欧拉图相关的生成与计数问题探究](https://oi.logey.cn/EulerPath.pdf)

#### 解法

题意转化一下就是说让原图 $G$ 的每条边建两遍，那么显然是一张欧拉回路。要求删去两条边之后这张图存在欧拉路径。

既然存在欧拉路径，那么必然存在两个或者零个奇度点。删去一条边会使得两个端点的度数减一，那么只存在以下三种合法的删边方式。

 1.删除两条自环（删除后为欧拉图）。
 2.删除两条有公共点的边（删除后为半欧拉图）。
 3.删除一条自环与一条边（删除后为半欧拉图）。
 
那么分别统计方案就可以了。

注意这张图不一定连通，可能存在无解的方案。需要想办法判断每条边是不是都走过了，我的代码里是是用 $dfs$ 判断了一下边的度数。

#### Source Code

```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>

const int MAXN = 1e6 + 7;

int f[MAXN], h[MAXN], self[MAXN];
int deg[MAXN], my, es;
int tot, t2;

struct Edge {
    int t, next;
} edge[MAXN << 1];

int head[MAXN], cnt;
bool vis[MAXN];
long long ans;

void add(int u, int v) {
    edge[++cnt] = (Edge){v, head[u]}; head[u] = cnt;
}

void dfs(int u) {
    tot += deg[u];
    t2 += self[u];
    vis[u] = true;

    ans += (1LL * deg[u] * (deg[u] - 1LL) / 2LL);
    for (int e = head[u]; e; e = edge[e].next) {
        int v = edge[e].t;
        if (!vis[v]) dfs(v);
    }
}

int main(int argc, char *argv[]) {
    int n, m, r;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        if (u == v) my++, self[u]++;
        else deg[u]++, deg[v]++, es++, add(u, v), add(v, u);
    }

    ans = 1LL * es * my + 1LL * (1LL * my * (my - 1)) / 2;

    for (int i = 1; i <= n; i++) {
        if (!vis[i] && deg[i]) {dfs(i); break;}
    }

    if (tot != es * 2) ans = 0;
    if (t2 != my) ans = 0;

    printf("%lld\n", tot == es * 2 ? ans : 0);
    return 0;
}
```