typedeflonglong ll; constint N = 18; ll dp[N][N]; int n, m; vector<int> e[N]; bool mp[N][N], b[N];
voiddfs(int u, int fa){ for (int i = 1; i <= n; i++) dp[u][i] = 1; for (int v : e[u]) { if (v == fa) continue; dfs(v, u); for (int i = 1; i <= n; i++) { ll sum = 0; for (int j = 1; j <= n; j++) { sum += dp[v][j] * (mp[i][j] & b[i] & b[j]); } dp[u][i] *= sum; } } }
intmain(){ scanf("%d %d", &n, &m); for (int i = 1; i <= m; i++) { int u, v; scanf("%d %d", &u, &v); mp[u][v] = mp[v][u] = 1; } for (int i = 1; i < n; i++) { int u, v; scanf("%d %d", &u, &v); e[u].push-back(v); e[v].push-back(u); } ll res = 0; for (int i = 1; i <= (1 << n) - 1; i++) { int size = 0; memset(b, 0, sizeof b); for (int j = 1; j <= n; j++) b[j] = ((i >> (j - 1)) & 1), size += !b[j]; dfs(1, 0); for (int i = 1; i <= n; i++) res = (size & 1) ? res - dp[1][i] : res + dp[1][i]; } printf("%lld\n", res); return0; }