HDU4997

Description

People are weak. Relationship between people like friendship or love is weak too. But a group of persons can have strong relationship, umm, 2-edge-connected relationship.

Suppose there are n persons. If two persons, A and B, are in a relationship, then we add an un-directional edge between them. In this way we can have a relationship graph, which is an un-directional graph without self-loops or multiple edges. If this graph is 2-edge-connected, then we say these persons have a strong relationship.

Now we have a group of persons without relationship between any two of them. And some pair of persons even hate each other. You will introduce some pairs of persons to know each other and set up a relationship between them to make the group of persons have a strong relationship. But notice that you can't set up a relationship between a pair of persons who hate each other. How many ways you can do that? (Two ways are different if there exists a pair of persons which have relationship in one way but not in another way).

output the answer modulo 1e9+7

Input

The first line contains an integer , denoting the number of the test cases.

For each test case, the first line contains 2 integers n and m, denoting the number of persons in the group and the number of pairs of persons who hate each other. Then m lines follow, each line containing 2 integers and , denoting that and B hate each other.

The persons are indexed from .

Output

For each test case, output the answer in a line.

Sample Input

3
5 0
10 0
5 2
1 2
2 3

Sample Output

253
466997276
18

Hint

A 2-edge-connected graph is a graph which is connected and if you remove an edge from it, it is still connected.

Note that , so we can ignore the issue that whether a single vertex is 2-edge-connected or not :).

Solution

1.计算集合 形成的连通图的方案数

直接做是 这里说一下 做法：定义集合幂级数的乘法为子集卷积， 为形成连通图的方案的集合幂级数， 为形成任意子图的方案的集合幂级数( 项的系数是 )

2. 计算集合 形成的双连通图的方案数

为计算双连通子图的方案 ，再记录一个h[S][T]表示将 划分为若干不相互连通的连通子集 使得所有子集 都有且仅有一条连向 的边 （两条就双连通了）

一开始特别菜的不知道怎么预处理这个 以为只能 一看其他人写的直接 即可，我容斥不过关

Code

#include<bits/stdc++.h>
#define ll long long
#define FIO "hdu4997"
using namespace std;

const int N=10,SN=1<<N,MOD=1e9+7,N2=N*N;

inline int add(int a,const int &b){return (a+=b)>=MOD?a-MOD:a;}
inline int sub(int a,const int &b){return (a-=b)<   0?a+MOD:a;}
inline int mul(const int &a,const int &b){return 1ll*a*b%MOD;}
inline int& inc(int &a,const int &b){return a=add(a,b);}
inline int& dec(int &a,const int &b){return a=sub(a,b);}
inline int& pro(int &a,const int &b){return a=mul(a,b);}
inline int qpow(int a,int b){int c=1;for(;b;b>>=1,pro(a,a))if(b&1)pro(c,a);return c;}
inline int inv(const int &a){return qpow(a,MOD-2);}

int n,T,m,d[N][N],E[SN],f[SN],g[SN][N+1],h[SN][SN],up,ans[SN],bin[N2];

inline void clear(){
  memset(d,0,sizeof d);
  memset(E,0,sizeof E);
  memset(f,0,sizeof f);
  memset(g,0,sizeof g);
  memset(h,0,sizeof h);
}

inline void add(int *a,int *b){for(int i=0;i<=n;i++)inc(a[i],b[i]);}
inline void sub(int *a,int *b){for(int i=0;i<=n;i++)dec(a[i],b[i]);}

inline void getln(int *f){
  static int tmp[N+1];
  for(int i=0;i<=n;i++)tmp[i]=f[i];
  for(int i=1;i<n;i++){
    int cur=0;
    for(int j=0;j<i;j++)inc(cur,mul(mul(j+1,f[j+1]),tmp[i-j]));
    dec(f[i+1],mul(inv(i+1),cur));
  }
}

inline int edge(int S,int T){return sub(E[S^T],add(E[S],E[T]));}

inline void getf(){
  for(int S=1;S<up;S++)g[S][__builtin_popcount(S)]=bin[E[S]];
  for(int S=1;S<up;S<<=1)for(int i=0;i<up;i++)if(i&S)add(g[i],g[i^S]);
  for(int S=1;S<up;S++)getln(g[S]);
  for(int S=1;S<up;S<<=1)for(int i=0;i<up;i++)if(i&S)sub(g[i],g[i^S]);
  for(int S=1;S<up;S++)f[S]=g[S][__builtin_popcount(S)];
}

inline void getans(){
  for(int S=0;S<up;S++)h[0][S]=1;
  for(int S=1;S<up;S++){
    int lst=S&-S;
    for(int T=up-1^S;T;T=(T-1)&(up-1^S))
      for(int s=S^lst;~s;s=s?(s-1)&(S^lst):-1)
        inc(h[S][T],mul(mul(h[S^s^lst][T],f[s^lst]),edge(s^lst,T)));
  }

  for(int S=0;S<up;S++){
    int lst=S&-S;
    ans[S]=f[S];
    if(S^lst)
    for(int s=(S^lst)&((S^lst)-1);~s;s=s?(s-1)&(S^lst):-1)
      dec(ans[S],mul(ans[s^lst],h[S^s^lst][s^lst]));
  }
}

int main(){
  freopen(FIO".in","r",stdin);
  //freopen(FIO".out","w",stdout);
  scanf("%d",&T);
  bin[0]=1;for(int i=1;i<N2;i++)bin[i]=add(bin[i-1],bin[i-1]);
  while(T--){
    clear();
    scanf("%d%d",&n,&m);
    up=1<<n;
    while(m--){
      int u,v;
      scanf("%d%d",&u,&v);
      u--;v--;
      d[u][v]++;
      d[v][u]++;
    }
    for(int S=0;S<up;S++)
      for(int i=0;i<n;i++)if(S>>i&1)
        for(int j=i+1;j<n;j++)if(S>>j&1)E[S]+=!d[i][j];

    getf();getans();

    printf("%d\n",ans[up-1]);
  }
  return 0;
}