2350. [HZOI 2015] Biconnected

【题目描述】

对于一个简单联通图,有些点之间的边不能连接,如果去掉图中任意一条边,这个图还是联通的,那么就是一个双联通的简单图,求N个点的双联通的简单图的个数对1e9+7取模的结果

【输入格式】

多组测试数据 第一行一个数表示数据组数

对于每组数据 第一行是两个数N,M,N表示图的点数,M表示图中禁止连接的点对数量

接下M行,每行两个数x,y,表示x,y之间不能连边,数据保证x和y是不同的点,且点的编号从1到N,数据还保证没有这样重复的关系

【输出格式】

对于每个数据输出一个数表示N个点的双联通的简单图的个数,结果对1e9+7取模

【样例输入】

3

5 0

10 0

5 2

1 2

2 3

【样例输出】

253

466997276

18

【数据范围和约定】

对于20%的数据 N<=4

对于另外30%的数据 M=0

对于100%的数据 2<=N<=10,M<=n*(n-1)/2