代码

#include <bits/stdc++.h>
#define int long long
const int MAXM = 2e6 + 20;
const int MAXN = 5e5 + 20;
const int MOD = 1e9 + 7;

int n, m;
int Pow[2000000 + 20];

int Ans = 0;
int SumeDCC[MAXN]; // eDCC 和, 隶属于 Graph1
int f[MAXN][2];
int Col[MAXN]; // eDCC 编号, 隶属于 Graph2
int SumTree[MAXN]; // 子树和, 隶属于 Graph2
int low[MAXN], dfn = 0;
class Graph_Class
{
private:

public:
    void dfs1(int Now, int fa)
    {
        low[Now] = ++dfn;
        for (int i = head[Now]; ~i; i = Edge[i].next)
        {
            int NowTo = Edge[i].to;

            if (NowTo == fa) continue;
            /*下降边*/
            if (!low[NowTo]) {
                dfs1(NowTo, Now);
            }
            low[Now] = std::min(low[Now], low[NowTo]);
        }
        SumeDCC[low[Now]]++;
    }

    void dfs2(int Now, int fa)
    {
        f[Now][0] = 1, f[Now][1] = Pow[SumeDCC[Now]] - 1;
        SumTree[Now] = 1;
        for (int i = head[Now]; ~i; i = Edge[i].next)
        {
            int NowTo = Edge[i].to;
            if (NowTo == fa) continue;
            dfs2(NowTo, Now);
            SumTree[Now] += SumTree[NowTo];

            int f0 = 0, f1 = 0;
            f0 = f[Now][0] * 2 % MOD * f[NowTo][0] % MOD;
            f1 = f[Now][1] * 2 % MOD * f[NowTo][0] % MOD;
            f1 = (f1 + f[Now][1] * f[NowTo][1] % MOD) % MOD;
            f1 = (f1 + f[Now][0] * f[NowTo][1] % MOD) % MOD;

            f[Now][0] = f0, f[Now][1] = f1;
        }

        if (Now == Col[1]) {
            Ans += f[Now][1] % MOD * Pow[m - SumTree[Now] + 1] % MOD;
            Ans %= MOD;
        }else {
            Ans += f[Now][1] % MOD * Pow[m - SumTree[Now]] % MOD;
            Ans %= MOD;
        }
    }

    struct node
    {
        int to, w;
        int next;
    } Edge[MAXM];
    int Edge_Cnt = 0;
    int head[MAXN];
    void head_init() { for (int i = 0; i <= n + 1; i++) head[i] = -1; }

    inline void addedge(int u, int v) {
        Edge[++Edge_Cnt].to = v, Edge[Edge_Cnt].w = 1;
        Edge[Edge_Cnt].next = head[u];
        head[u] = Edge_Cnt;
    }
} Graph1, Graph2;

class Sol_Class
{
private:
    int cnt = 0;

public:
    /*e-DCC 缩点*/
    void eDCC()
    {
        Graph1.dfs1(1, -1);
        for (int i = 1; i <= n; i++) {
            Col[i] = low[i];
        }

        Graph2.head_init();
        for (int i = 1; i <= n; i++) {
            int u = Col[i];
            for (int j = Graph1.head[i]; ~j; j = Graph1.Edge[j].next) {
                int v = Col[Graph1.Edge[j].to];
                if (u != v) Graph2.addedge(u, v); 
            }
        }
    }

    /*树形 dp*/
    void solve()
    {
        Graph2.dfs2(Col[1], -1);
        printf("%lld", Ans);
    }
} Sol;

signed main()
{
    scanf("%lld %lld", &n, &m);
    Graph1.head_init();
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%lld %lld", &u, &v);

        Graph1.addedge(u, v);
        Graph1.addedge(v, u);
    }
    Pow[0] = 1;
    for (int i = 1; i <= 1e6; i++) {
        Pow[i] = (Pow[i - 1] * 2) % MOD; 
    }
    Sol.eDCC();
    Sol.solve();

    return 0;
}