传送门

选一个边的子集可以看作在原图上删边。图中的每个连通块都是独立的,我们可以分开考虑。对每个连通块,我们可以跑出一个生成树,当每条非树边都确定了删或不删后,剩下的树边能确定出一个唯一的方案。所以整个连通块的方案数为$2^{m-n+1}$,其中$m$为边数,$n$为点数,也就是说整个图的方案数为$2^{m-n+c}$,其中$c$为连通块数。

题目要统计的是平方和,当我们删了$x$条边时,对答案的贡献是$(m-x)^2=m^2-2mx+x^2$,前两项要我们统计删边的方案数,以及对于每条边,钦定它删除的方案数之和,都很好统计。最后一项比较麻烦,需要统计对于每两条边,把它们都删除后的方案数之和。根据两条边删掉之后连通块数量的改变,可能会出现不同的情况。两条边中有桥边的情况比较特殊,但也比较好统计,我们单独处理,然后就只用考虑两条边都非桥边的情况了。这里可以用和DZY Loves Chinese II一样的方法,给每条非树边随机一个较大权值(unsigned long long 范围内),然后令树边的权值为所有跨过它的非树边的权值的异或和。这样,因为两条边非桥的树边同时删除后连通块数量会增加当且仅当不存在非树边跨过了其中其中一条,而没有跨过另一条,我们可以认为这等价于两条边的权值相等。所以把所有的边按权值排序后,就可以对于每个不同的权值处理两条边都为这个权值的情况,剩下的就是两条边删掉之后连通块数量不变的情况,可以直接处理。

#include <bits/stdc++.h>
#define MAXN 200010
#define ULL unsigned long long
#define LL long long
using namespace std;

const LL P=1000000007;

struct edge{
    int to,next;
    edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN<<1];

ULL get_rand(){
    ULL res=0;
    for(int i=0;i<8;i++) res=res<<8|(rand()&255);
    return res;
}

int n,m,numc;
LL p2[MAXN];
int g[MAXN],nume,prei[MAXN];
bool visit[MAXN];
int e2[MAXN][3];
ULL ve[MAXN],d[MAXN];

void addEdge(int u,int v){
    e[nume]=edge(v,g[u]);
    g[u]=nume++;
}

void dfs(int x){
    visit[x]=1;
    for(int i=g[x];~i;i=e[i].next)
        if(!visit[e[i].to]){
            prei[e[i].to]=i;
            e2[i/2+1][2]=1;
            dfs(e[i].to);
        }
}

void dfs2(int x){
    for(int i=g[x];~i;i=e[i].next)
        if(prei[e[i].to]==i){
            dfs2(e[i].to);
            ve[i/2+1]=d[e[i].to];
            d[x]^=d[e[i].to];
        }
}

LL cnt0(){ 
    return p2[m-n+numc]; 
}

LL cnt1(){
    LL res=0;
    for(int i=1;i<=m;i++)
        if(ve[i]) res=(res+p2[m-1-n+numc])%P;
        else res=(res+p2[m-1-n+numc+1])%P;
    return res;
}

LL cnt2(){
    int last;
    for(int i=1;i<=m;i++)
        if(ve[i]){
            last=i-1;
            break;
        }
    LL res=0;
    if(last){
        res=(res+p2[m-2-n+numc+2]*last%P*(last-1))%P;
        res=(res+p2[m-2-n+numc+1]*last%P*(m-last)%P*2)%P;
    }
    for(int i=last+1;i<=m;i++)
        if(i==m || ve[i]!=ve[i+1]){
            int len=i-last;
            res=(res+p2[m-2-n+numc+1]*len%P*(len-1))%P;
            res=(res+p2[m-2-n+numc]*len%P*(m-i)%P*2)%P;
            last=i;
        }
    return res;
}

int main(){
#ifdef DEBUG
    freopen("108.in","r",stdin);
#endif
    memset(g,-1,sizeof g);
    memset(prei,-1,sizeof prei);
    p2[0]=1;
    for(int i=1;i<MAXN;i++) p2[i]=p2[i-1]*2%P;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        e2[i][0]=u; e2[i][1]=v;
        addEdge(u,v);
        addEdge(v,u);
    }
    for(int i=1;i<=n;i++)
        if(!visit[i]){
            dfs(i);
            numc++;
        }
    for(int i=1;i<=m;i++)
        if(!e2[i][2]){
            ve[i]=get_rand();
            d[e2[i][0]]^=ve[i];
            d[e2[i][1]]^=ve[i];
        }
    for(int i=1;i<=n;i++)
        if(prei[i]==-1)
            dfs2(i);
    sort(ve+1,ve+m+1);
    LL c0=cnt0(),c1=cnt1(),c2=cnt2();
    c2=(c2+c1)%P;
    LL ans=(c0*m%P*m%P-c1*2*m%P+c2)%P;
    if(ans<0) ans+=P;
    printf("%lld\n",ans);
    return 0;
}