本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。

//It is made by ljh2000

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

typedef long long LL;

#define RG register

const int MAXN = 19;

const int MAXM = 520;

int n,m,ecnt,first[MAXN],to[MAXM],next[MAXM],all;

int mp[MAXN][MAXN],cnt,a[MAXN];

int head[MAXN],match[MAXN];

LL ans,f[MAXN][MAXN];//f[i][j]表示以i为根的子树的方案数，其中i对应的是j

struct edge{ int to,next; }e[MAXM];

inline void link(int x,int y){ next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y; }

inline void Link(int x,int y){ e[++ecnt].next=head[x]; head[x]=ecnt; e[ecnt].to=y; }

inline int getint(){

    int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();

    if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;

}

inline void dp(RG int x,RG int fa){

	RG int i,s1,j,k; for(i=first[x];i;i=next[i]) { if(to[i]==fa) continue; dp(to[i],x); }

	RG LL now=0;

	for(s1=1;s1<=cnt;++s1) {//枚举当前子树的根选什么

		f[x][s1]=1;

		for(j=first[x];j;j=next[j]) {

			if(to[j]==fa) continue; now=0;

			for(k=head[a[s1]];k;k=e[k].next) now+=f[to[j]][ match[e[k].to] ];

			f[x][s1]*=now;

			if(f[x][s1]==0) break;//剪枝...

		}

	}

}

inline void work(){

	n=getint(); m=getint(); all=(1<<n)-1; RG int i,j,x,y; RG LL now;

	for(i=1;i<=m;++i) { x=getint(); y=getint(); mp[x][y]=mp[y][x]=1; }

	for(i=1;i<n;++i) { x=getint(); y=getint(); link(x,y); link(y,x); }

	for(i=1;i<=all;++i) {

		x=i; cnt=0;

		for(j=1;j<=n;++j) {

			if(x&1) a[++cnt]=j; match[j]=cnt;

			x>>=1; if(x==0) break;

		}

		ecnt=0; memset(head,0,sizeof(head));

		for(j=1;j<=cnt;j++)

			for(y=1;y<=cnt;y++)

				if(mp[ a[j] ][ a[y] ])

					Link(a[j],a[y]);

		dp(1,0);

		now=0;

		for(j=1;j<=cnt;++j) now+=f[1][j];

		if((cnt&1) == (n&1)) ans+=now;

		else ans-=now;

	}

	printf("%lld",ans);

}

int main()

{

    work();

    return 0;

}