复杂度应该是 $O(n^3\times 2^n)$，题解区说能过，结果 T 成 60。
LOJ 上最慢点 1049ms
乱卡一通反而变慢了亿点点
救救孩子吧。。。（

//愿你有一天能和你重要的人重逢。
#include<bits/stdc++.h>
#define ri register int
#define ci const int &
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
	x=0;char c=getchar(),f=0;
	for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=1;
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	if(f) x=-x;
}
char ban[18],mp[18][18];ll res,dp[18][18];int n,m;
int et,head[18];struct edge{int to,nxt;}e[36];
inline void adde(ci x,ci y) {e[++et]=(edge){y,head[x]},head[x]=et;}
inline void dfs(ci x,ci fa)
{
	for(ri i=1;i<=n;i++) dp[x][i]=1;
	for(ri i=head[x];i;i=e[i].nxt) if(e[i].to^fa)
	{
		dfs(e[i].to,x);
		for(ri j=1;j<=n;j++)
		{
			ll sm=0;
			for(ri k=1;k<=n;k++) if(mp[k][j]&&!ban[k]&&!ban[j]) sm+=dp[e[i].to][k];
			dp[x][j]*=sm;
		}
	}
}
int main()
{
	read(n),read(m);for(ri i=1,x,y;i<=m;i++) read(x),read(y),mp[x][y]=mp[y][x]=1;
	for(ri i=1,x,y;i<n;i++) read(x),read(y),adde(x,y),adde(y,x);
	for(ri S=0;S<(1<<n);S++)
	{
		memset(ban,0,sizeof(ban));int cnt=0;
		for(int i=1,T=S;i<=n;i++,T>>=1) if(T&1) ban[i]=1,cnt++;
		dfs(1,0);ll rs=0;for(int i=1;i<=n;i++) rs+=dp[1][i];
		res+=cnt&1?-rs:rs;
	}
	return printf("%lld\n",res),0;
}