#include #define fi first #define se second #define mp make_pair #define ll long long #define ull unsigned ll #define db double #define pii pair #define vi vector #define e emplace #define eb emplace_back //#define int ll using namespace std; const ll inf=1073741800,INF=4611686018427387000,MOD=1e9+7; namespace FastIO { template inline void read(T&x) { x=0;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); bool tf=(ch=='-')&&(ch=getchar()); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); tf?x=-x:0; } inline void write(int x,char ch=' ') { if(x<0)putchar('-'),x=-x; char st[50];int top=0; do st[++top]=x%10+'0',x/=10;while(x); while(top)putchar(st[top--]); ch!='~'?putchar(ch),0:0; } template inline void read(T&x,Args &...args){read(x),read(args...);} } using namespace FastIO; namespace MTool { inline int Cadd(int x,int y){return x+y>=MOD?(x+y-MOD):(x+y);} inline int Cdel(int x,int y){return x=MOD?(x+y-MOD):(x+y));} inline void Mdel(int&x,int y){x=(x T[100010]; pii a[100010]; int f[100010][2][2],deg[100010]; //f*0:can't //f*1:must int fr[100010]; int b[100010]; int real[100010]; int g[100010][3][3],h[100010][2][3],g2[100010][3][3]; void dfs(int x,int fa=0) { if(x!=1&&T[x].size()==1) return f[x][0][1]=1,void(); memset(g[x],0,sizeof(g[x])); g[x][0][1]=1; for(auto P:T[x])if(P.fi!=fa) { int to=P.fi,v=P.se; dfs(to,x); memset(h[x],0,sizeof(h[x])); h[x][0][0]=f[to][0][0]; h[x][0][2]=f[to][0][1]; h[x][1][0]=f[to][1][0]; h[x][1][2]=f[to][1][1]; if(real[v])Mdel(h[x][1][1],Cadd(f[to][0][1],f[to][1][1])); memset(g2[x],0,sizeof(g2[x])); // if(to==3) // { // cerr<1) { Madd(f[x][1][0],Cmul(Cadd(g[x][2][0],g[x][2][1]),fr[deg[x]-2])); Madd(f[x][1][1],Cmul(Cadd(g[x][1][1],g[x][1][2]),fr[deg[x]-2])); } } inline void mian() { int x,y; read(n,m); for(int i=1;i<=n;++i) { f[i][0][0]=f[i][0][1]=0; f[i][1][0]=f[i][1][1]=0; deg[i]=0; T[i].clear(); } for(int i=1;i