#include #include #include #include const int N=1e5+7,mod=1e9+7;typedef long long ll;const ll Mod=mod; ll qpow(ll x,int y){ll r=1;for(;y;x=x*x%Mod,y>>=1)if(y&1)r=r*x%Mod;return r;} inline void radd(int&a,int b){(a+=b)>=mod&&(a-=mod);} int fi() { int r,ch;bool f=0;while(!isdigit(ch=getchar()))if(ch=='-')f=1; r=(ch^48);while(isdigit(ch=getchar()))r=r*10+(ch^48);return f?-r:r; } int frc[N],inv[N]; int U[N],V[N],dep[N],vl[N]; std::vector to[N]; ll mans,zans;bool ez[N]; void dfs(int i,int l) { dep[i]=dep[l]+1;vl[i]=inv[to[i].size()-1]; mans=(ll)mans*frc[to[i].size()-1]%Mod; for(int v:to[i])if(v!=l)dfs(v,i); } int f[N]; /*1 begin 2 end 3 connect*/ void Dfs(int i,int l) { if(ez[i])f[i]=1;//1 else f[i]=0; int sum=0;//dwn->nw sumf for(int v:to[i])if(v!=l) { Dfs(v,i); if(!ez[i])f[i]=(f[i]+(ll)f[v]*vl[i])%Mod; else zans=(zans+(ll)f[v]*vl[i])%Mod;//2 zans=(zans+(ll)f[v]*sum%Mod*vl[i])%Mod;//3 radd(sum,f[v]); } } int main() { *frc=1;for(int i=1;i<=1e5;++i)frc[i]=(ll)frc[i-1]*i%Mod; inv[1]=1;for(int i=2;i<=1e5;++i)inv[i]=(Mod-Mod/i)*inv[mod%i]%Mod; freopen("traverse.in","r",stdin); freopen("traverse.out","w",stdout); int cas=fi(),T=fi(),n,k; while(T--) { n=fi();k=fi();for(int i=1;i<=n;++i)to[i].clear(),ez[i]=0; for(int i=1;i