T448081 生成树

给定一张连通图，保证不存在从$1$号点开始经过$8$个点的简单路径（简单路径就是不经过重复点的路径），求生成树个数

第一行一个数$T$表示数据组数 每组数据第一行两个数$n,m$，表示点数和边数 接下来$m$行，每行两个数表示一条无向边

每组数据输出一行一个整数，表示答案模$2^{30}$

对于20%的数据, $n,m \le 200$ 对于50%的数据,$n,m \le 10000$ 对于100%的数据，$1 \le T \le 10,1 \le n \le 50000, 1 \le m \le 50000$