<commit_before><commit_msg>洛谷3349<commit_after>#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC target("avx")
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<stack>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MAXN=17;
const int MAXM=40;
struct node{
    int nxt,v;
}Edge[MAXM];
int head[MAXN],cnt_e;
inline void add(int u,int v)
{
    Edge[++cnt_e].v=v;
    Edge[cnt_e].nxt=head[u];
    head[u]=cnt_e;
}
unsigned char mp[20][20];
ll f[20][20],sum,ans;
int n,m,a[20],cnt,x,y;
void dfs(int x,int fa)
{
    for(int i=1;i<=cnt;i++) f[x][i]=1;
    for(int i=head[x];i;i=Edge[i].nxt)
    {
        int v=Edge[i].v;
        if(v==fa) continue;
        dfs(v,x);
        for(int j=1;j<=cnt;j++)
        {
            ll tmp=0;
            for(int k=1;k<=cnt;k++)
                if(mp[a[j]][a[k]]) tmp+=f[v][k];
            f[x][j]*=tmp;
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d%d",&x,&y),mp[x][y]=mp[y][x]=1;
    for(int i=1;i<n;i++)  scanf("%d%d",&x,&y),add(x,y),add(y,x);
    for(int s=1;s<(1<<n);s++)
    {
        cnt=sum=0;
        for(int i=0;i<=n-1;i++) if((s>>i)&1)  a[++cnt]=i+1;
        dfs(1,0);
        for(int i=1;i<=cnt;i++) sum+=f[1][i];
        if((n-cnt)&1) ans-=sum;
        else ans+=sum;
    }
    printf("%lld\n",ans);
}

{'fraction_non_alphanumeric': 0.23809523809523808, 'fraction_numerical': 0.02350030921459493, 'mean_word_length': 3.5577464788732396, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1252670', 'n_tokens_mistral': 749, 'n_tokens_neox': 727, 'n_words': 115}