stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <iostream>

using namespace std;

int A,B,C,X,Y;

int main() {

	cin>>A>>B>>C>>X>>Y;

	int sum=0;

	int minm=min(X,Y);

	if(2*C>A+B){

		sum+=minm*(A+B);

	}

	else

		sum+=minm*2*C;

	if(minm==X){

		int d=Y-X;

		if(C*2>B)

		sum+=d*B;

		else

		sum+=d*2*C;

	}

	else if(minm==Y){

		int d=X-Y;

		if(C*2>A)

		sum+=d*A;

		else

		sum+=d*2*C;

	}

	cout<<sum<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.244602346230533x):
#include<stdio.h>

#include<algorithm>

using namespace std;



int a,b,c,x,y;



int main(){

//	freopen("inb.txt","r",stdin);

	scanf("%d%d%d%d%d", &a, &b, &c, &x, &y);

	int com = min(x,y);//a b棋盘公共的部分 com套a+b 

	int sum = 0; 

	if(a+b>=c*2){//套装更优惠 

		sum += com*c*2; 

		if(x>=y){

			if(a>=c*2){

				sum += (x-y)*2*c;

			}else{

				sum += (x-y)*a;

			}	

		}else{

			if(b>=c*2){

				sum += (y-x)*2*c;

			}else{

				sum += (y-x)*b;

			}

		}

	}else{//单买更优惠 

		sum = x*a + y*b; 

	}

	printf("%d\n", sum);

	

	return 0;

}
// Slower C++ solution:
//ツ暗。ツつ、ツづァツつオツつ「

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <utility>

using namespace std;

struct road{

	int a,b,l;

	road(int a_,int b_,int l_):a(a_),b(b_),l(l_){}

};

typedef pair<int,int> pii;

int main(){

	int n,m,k,a,b,l,s;

	vector<road> rd;

	vector<pii> town[3001];

	int len[3001];

	priority_queue<pii,vector<pii>,greater<pii> > qu;

	int inf = 1e9;



	for(cin>>n>>m>>k;m--;rd.push_back(road(a,b,l))){

		cin>>a>>b>>l;

		town[a].push_back(make_pair(b,l));

		town[b].push_back(make_pair(a,l));

	}

	for(;k--;qu.push(make_pair(0,s)))

		cin>>s;



	for(fill(len,len+n+1,-1);!qu.empty();){

		pii pi = qu.top();

		qu.pop();

		if( len[pi.second] == -1 ){

			len[pi.second] = pi.first;

			for(

				vector<pii>::iterator it=town[pi.second].begin();

				it != town[pi.second].end();

				++it

			){

				qu.push(make_pair(pi.first+it->second,it->first));

			}

		}

	}

	

	s=0;

	for(vector<road>::iterator it = rd.begin(); it != rd.end();	++it ){

		s = max(max( s, len[a] ),

				max( len[b], (len[it->b] + it->l - len[it->a] + 1)/2 + len[it->a] )

		);

	}

	cout << s << endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.1675830352862557x):
#include <cstdio>

#include <queue>

#include <vector>

#include <algorithm>

#include <utility>

#include <functional>

using namespace std;



typedef pair<int,int> pii;



int main(){

	int n, m, k, u;

	scanf("%d%d%d", &n, &m, &k);



	vector<int> a(m), b(m), L(m);

	vector<vector<pii> > G(n + 1);

	for(int i = 0; i < m; ++i){

		scanf("%d%d%d", &a[i], &b[i], &L[i]);

		G[a[i]].push_back(pii(L[i], b[i]));

		G[b[i]].push_back(pii(L[i], a[i]));

	}



	priority_queue<pii,vector<pii>,greater<pii> > pq;

	vector<int> d(n + 1, 500000000);

	for(int i = 0; i < k; ++i){

		scanf("%d", &u);

		d[u] = 0;

		pq.push(pii(0, u));

	}



	while(!pq.empty()){

		int e = pq.top().first;

		u = pq.top().second;

		pq.pop();

		if(d[u] != e){ continue; }

		for(size_t i = 0; i < G[u].size(); ++i){

			int v = G[u][i].second;

			int f = e + G[u][i].first;

			if(d[v] > f){

				d[v] = f;

				pq.push(pii(f, v));

			}

		}

	}



	int ans = 0;

	for(int i = 0; i < m; ++i){

		int e = d[a[i]];

		int f = d[b[i]];

		int r = max(max(e, f), e + (f - e + L[i] + 1) / 2);

		ans = max(ans, r);

	}

	printf("%d\n", ans);

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <utility>

using namespace std;struct road{int a,b,l;road(int a_,int b_,int l_):a(a_),b(b_),l(l_){}};typedef pair<int,int> pii;int main(){int n,m,k,a,b,l,s;vector<road> rd;vector<pii> town[3001];int len[3001];priority_queue<pii,vector<pii>,greater<pii> > qu;for(cin>>n>>m>>k;m--;rd.push_back(road(a,b,l))){cin>>a>>b>>l;town[a].push_back(make_pair(b,l));town[b].push_back(make_pair(a,l));}for(;k--;qu.push(make_pair(0,s)))cin>>s;for(fill(len,len+n+1,-1);!qu.empty();){pii pi = qu.top();qu.pop();if( len[pi.second] == -1 ){len[pi.second] = pi.first;for(vector<pii>::iterator it=town[pi.second].begin();it != town[pi.second].end();++it){qu.push(make_pair(pi.first+it->second,it->first));}}}s=0;for(vector<road>::iterator it = rd.begin(); it != rd.end();++it ){s = max(max( s, len[a] ),max( len[b], (len[it->b] + it->l - len[it->a] + 1)/2 + len[it->a] ));}cout << s << endl;}

// Faster C++ solution for the same problem (measured speedup: 1.1675830352862557x):
#include <cstdio>

#include <queue>

#include <vector>

#include <algorithm>

#include <utility>

#include <functional>

using namespace std;



typedef pair<int,int> pii;



int main(){

	int n, m, k, u;

	scanf("%d%d%d", &n, &m, &k);



	vector<int> a(m), b(m), L(m);

	vector<vector<pii> > G(n + 1);

	for(int i = 0; i < m; ++i){

		scanf("%d%d%d", &a[i], &b[i], &L[i]);

		G[a[i]].push_back(pii(L[i], b[i]));

		G[b[i]].push_back(pii(L[i], a[i]));

	}



	priority_queue<pii,vector<pii>,greater<pii> > pq;

	vector<int> d(n + 1, 500000000);

	for(int i = 0; i < k; ++i){

		scanf("%d", &u);

		d[u] = 0;

		pq.push(pii(0, u));

	}



	while(!pq.empty()){

		int e = pq.top().first;

		u = pq.top().second;

		pq.pop();

		if(d[u] != e){ continue; }

		for(size_t i = 0; i < G[u].size(); ++i){

			int v = G[u][i].second;

			int f = e + G[u][i].first;

			if(d[v] > f){

				d[v] = f;

				pq.push(pii(f, v));

			}

		}

	}



	int ans = 0;

	for(int i = 0; i < m; ++i){

		int e = d[a[i]];

		int f = d[b[i]];

		int r = max(max(e, f), e + (f - e + L[i] + 1) / 2);

		ans = max(ans, r);

	}

	printf("%d\n", ans);

}
// Slower C++ solution:
#include<iostream>

#include<algorithm>

#include<vector>

#include<queue>

#include<utility>

using namespace std;struct road{int a,b,l;road(int a_,int b_,int l_):a(a_),b(b_),l(l_){}};typedef pair<int,int> pii;int main(){int n,m,k,a,b,l,s;vector<road>rd;vector<pii>town[3001];int len[3001];priority_queue<pii,vector<pii>,greater<pii> >qu;for(cin>>n>>m>>k;m--;rd.push_back(road(a,b,l))){cin>>a>>b>>l;town[a].push_back(make_pair(b,l));town[b].push_back(make_pair(a,l));}for(;k--;qu.push(make_pair(0,s)))cin>>s;for(fill(len,len+n+1,-1);!qu.empty();){pii pi=qu.top();qu.pop();if(len[pi.second]==-1){len[pi.second]=pi.first;for(vector<pii>::iterator it=town[pi.second].begin();it!=town[pi.second].end();++it)qu.push(make_pair(pi.first+it->second,it->first));}}s=0;for(vector<road>::iterator it=rd.begin();it!=rd.end();++it){s=max(max(s,len[a]),max(len[b],(len[it->b]+it->l-len[it->a]+1)/2+len[it->a]));}cout<<s<<endl;}

// Faster C++ solution for the same problem (measured speedup: 1.1675830352862557x):
#include <cstdio>

#include <queue>

#include <vector>

#include <algorithm>

#include <utility>

#include <functional>

using namespace std;



typedef pair<int,int> pii;



int main(){

	int n, m, k, u;

	scanf("%d%d%d", &n, &m, &k);



	vector<int> a(m), b(m), L(m);

	vector<vector<pii> > G(n + 1);

	for(int i = 0; i < m; ++i){

		scanf("%d%d%d", &a[i], &b[i], &L[i]);

		G[a[i]].push_back(pii(L[i], b[i]));

		G[b[i]].push_back(pii(L[i], a[i]));

	}



	priority_queue<pii,vector<pii>,greater<pii> > pq;

	vector<int> d(n + 1, 500000000);

	for(int i = 0; i < k; ++i){

		scanf("%d", &u);

		d[u] = 0;

		pq.push(pii(0, u));

	}



	while(!pq.empty()){

		int e = pq.top().first;

		u = pq.top().second;

		pq.pop();

		if(d[u] != e){ continue; }

		for(size_t i = 0; i < G[u].size(); ++i){

			int v = G[u][i].second;

			int f = e + G[u][i].first;

			if(d[v] > f){

				d[v] = f;

				pq.push(pii(f, v));

			}

		}

	}



	int ans = 0;

	for(int i = 0; i < m; ++i){

		int e = d[a[i]];

		int f = d[b[i]];

		int r = max(max(e, f), e + (f - e + L[i] + 1) / 2);

		ans = max(ans, r);

	}

	printf("%d\n", ans);

}
// Slower C++ solution:
#include<iostream>

#include<queue>

#include<map>

#include<cstdio>

#include<cmath>

#define INF 500000000

using namespace std;



typedef pair<int,int> P;



int n,m,k;

int l[100100],a[100100],b[100100];

vector<P> g[5000];

int d[5000],w[5000];

int s[5000];



int main(){

  cin >> n >> m >> k;

  for(int i=0;i<m;i++){

    cin >> a[i] >> b[i] >> l[i];

    a[i]--; b[i]--;

    g[a[i]].push_back(P(l[i],b[i]));

    g[b[i]].push_back(P(l[i],a[i]));

  }

 

  for(int i=0;i<k;i++){cin >> s[i]; s[i]--;}



  for(int i=0;i<n;i++)d[i] = INF;

  priority_queue<P,vector<P>,greater<P> > q;

  for(int i=0;i<k;i++){

    d[s[i]] = 0;

    q.push(P(0,s[i]));

  }



  while(q.size()){

    P p = q.top(); q.pop();

    int cost = p.first, pos = p.second;

    

    for(int i=0;i<(int)g[pos].size();i++){

      int dis = cost + g[pos][i].first;

      int next = g[pos][i].second;

      

      if(dis<d[next]){

	d[next] = dis;

	q.push(P(dis,next));

      }

    }

  }



  double ans = 0.0;

  for(int i=0;i<m;i++){

    if(fabs(d[a[i]] - d[b[i]]) >= l[i]){

      ans = max(ans,(double)max(d[a[i]],d[b[i]]));

    }else{

      ans = max(ans,(double)(l[i]+d[a[i]]+d[b[i]])/2);

    }

  }

  cout << (int)(ans+1e-9+0.5) << endl;

}

  

// Faster C++ solution for the same problem (measured speedup: 1.1210588643159158x):
#include<bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;

typedef pair<int,int> edge;



const int INF = 1e9;



int main(){

  int n,m,k;

  scanf("%d%d%d",&n,&m,&k);

  

  vector< vector<edge> > g(n);

  rep(i,m){

    int a,b,l;

    cin >> a >> b >> l; a--; b--;

    g[a].push_back(edge(l,b));

    g[b].push_back(edge(l,a));

  }



  vector<int> d(n,INF);

  priority_queue< edge, vector<edge>, greater<edge> > q;

  rep(i,k){

    int s; cin >> s; s--;

    d[s] = 0;

    q.push(edge(0,s));

  }



  while(q.size()){

    edge x = q.top(); q.pop();

    int c = x.first, v = x.second;

    

    for(edge e : g[v]){

      int nc = c + e.first;

      int u = e.second;

      

      if(d[u] > nc){

	d[u] = nc;

	q.push( edge(nc, u) );

      }

    }

  }

  

  int ans = 0;

  rep(a,n){

    for(edge e : g[a]){

      int l = e.first, b = e.second;

      

      int A = min(d[a], d[b]), B = max(d[a], d[b]);

      if(A+l < B){

	ans = max(ans, A+l);

      }else{

	ans = max(ans, (A+B+l+1)/2);

      }

    }

  }

  cout << ans << endl;

}
// Slower C++ solution:
#include <cstdio>

#include <iostream>

#include <vector>

using namespace std;

const int N = 5010, mod = 1e9 + 7;

int n, x, y, dp[N][N], siz[N], tmp[N], g[N];

vector<int> G[N];

void dfs(int u, int fa) {

    siz[u] = 1; 

    dp[u][1] = 1;

    for(auto v : G[u]) {

        if(v == fa) continue;

        dfs(v, u);

        for(int i = 1; i <= siz[u] + siz[v]; ++i) tmp[i] = 0;

        for(int i = 1; i <= siz[u]; ++i)

            for(int j = 0; j <= siz[v]; ++j)

                (tmp[i + j] += 1ll * dp[u][i] * dp[v][j] % mod) %= mod;

        siz[u] += siz[v];

        for(int i = 1; i <= siz[u]; ++i) dp[u][i] = tmp[i];

    }

    for(int i = 2; i <= siz[u]; i += 2)

        (dp[u][0] += 1ll * dp[u][i] * g[i] % mod) %= mod;

    if(fa) dp[u][0] = mod - dp[u][0];

}

int main() {

    scanf("%d", &n);

    for(int i = 1; i < n; ++i) {

        scanf("%d %d", &x, &y);

        G[x].push_back(y); 

        G[y].push_back(x);

    }

    g[0] = 1;

    for(int i = 2; i <= n; i += 2)

        g[i] = 1ll * g[i - 2] * (i - 1) % mod;

    dfs(1, 0);

    printf("%d\n", dp[1][0]);

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.1326995828908222x):
#include <bits/stdc++.h>

using namespace std;



#define Int register int

#define mod 1000000007

#define MAXN 5005



template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}

template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}

template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}



int mul (int a,int b){return 1ll * a * b % mod;}

int dec (int a,int b){return a >= b ? a - b : a + mod - b;}

int add (int a,int b){return a + b >= mod ? a + b - mod : a + b;}



int n,top = 1,to[MAXN << 1],nxt[MAXN << 1],head[MAXN],t[MAXN],g[MAXN],dp[MAXN][MAXN],siz[MAXN];

void Add_Edge (int u,int v){

	to[++ top] = v,nxt[top] = head[u],head[u] = top;

	to[++ top] = u,nxt[top] = head[v],head[v] = top;

}

void dfs (int u,int fa){

	siz[u] = dp[u][1] = 1;

	for (Int i = head[u];i;i = nxt[i]){

		int v = to[i];

		if (v == fa) continue;

		dfs (v,u);

		for (Int j = 0;j <= siz[u];++ j) t[j] = dp[u][j],dp[u][j] = 0;

		for (Int j = 0;j <= siz[u];++ j)

			for (Int k = 0;k <= siz[v];++ k)

				dp[u][j + k] = add (dp[u][j + k],mul (dp[v][k],t[j]));

		siz[u] += siz[v]; 

	}

	for (Int i = 1;i <= siz[u];++ i) dp[u][0] = dec (dp[u][0],mul (dp[u][i],i & 1 ? 0 : g[i]));

}



signed main(){

	read (n);

	for (Int i = 2,u,v;i <= n;++ i) read (u,v),Add_Edge (u,v);

	g[0] = 1;for (Int i = 2;i <= n;++ i) g[i] = mul (g[i - 2],i - 1);

	dfs (1,0),write (dec (0,dp[1][0])),putchar ('\n');

	return 0;

}
// Slower C++ solution:
#include <cstdio>

#include <algorithm>

using namespace std;



const int MAXN = 5000;

const int MOD = int(1E9) + 7;

const int INV2 = (MOD + 1) >> 1;



struct edge{

	edge *nxt; int to;

}edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt = edges;

void addedge(int u, int v) {

	edge *p = (++ecnt);

	p->to = v, p->nxt = adj[u], adj[u] = p;

	p = (++ecnt);

	p->to = u, p->nxt = adj[v], adj[v] = p;

}



int fct[MAXN + 5], ifct[MAXN + 5], coef[MAXN + 5];

void init() {

	fct[0] = 1;

	for(int i=1;i<=MAXN;i++)

		fct[i] = 1LL*fct[i-1]*i%MOD;

	ifct[1] = 1;

	for(int i=2;i<=MAXN;i++)

		ifct[i] = (MOD - 1LL*(MOD/i)*ifct[MOD%i]%MOD);

	ifct[0] = 1;

	for(int i=1;i<=MAXN;i++)

		ifct[i] = 1LL*ifct[i-1]*ifct[i]%MOD;

	int t = INV2;

	for(int i=2;i<=MAXN;i+=2,t=1LL*t*INV2%MOD)

		coef[i] = 1LL*fct[i]*ifct[i/2]%MOD*t%MOD;

}



int dp[MAXN + 5][MAXN + 5], siz[MAXN + 5];

void dfs(int x, int f) {

	dp[x][siz[x] = 1] = 1;

	for(edge *p=adj[x];p;p=p->nxt) {

		if( p->to == f ) continue;

		dfs(p->to, x);

		int t1 = siz[x], t2 = siz[p->to], del = 0;

		for(int i=2;i<=t2;i+=2)

			del = (del + 1LL*dp[p->to][i]*coef[i]%MOD) % MOD;

		del = (MOD - del) % MOD;

		for(int i=t1;i>=1;i--) {

			for(int j=t2;j>=1;j--)

				dp[x][i+j] = (dp[x][i+j] + 1LL*dp[x][i]*dp[p->to][j]%MOD) % MOD;

			dp[x][i] = 1LL*del*dp[x][i] % MOD;

		}

		siz[x] += siz[p->to];

	}

}



int main() {

	int N; init();

	scanf("%d", &N);

	for(int i=1;i<N;i++) {

		int x, y; scanf("%d%d", &x, &y);

		addedge(x, y);

	}

	dfs(1, 0);

	int ans = 0;

	for(int i=1;i<=N;i++)

		ans = (ans + 1LL*dp[1][i]*coef[i]%MOD) % MOD;

	printf("%d\n", ans);

}

// Faster C++ solution for the same problem (measured speedup: 1.9025452462875438x):
#include <cstdio>



const int MAXN = 5000, MOD = 1e9 + 7;

int n, ecnt, head[MAXN + 5], siz[MAXN + 5];

int g[MAXN + 5], f[MAXN + 5][MAXN + 5];



struct Edge { int to, nxt; } graph[MAXN * 2 + 5];



inline void addeq ( int& a, const int b ) { if ( ( a += b ) >= MOD ) a -= MOD; }



inline void link ( const int s, const int t ) {

	graph[++ ecnt] = { t, head[s] };

	head[s] = ecnt;

}



inline void solve ( const int u, const int fa ) {

	static int tmp[MAXN + 5];

	f[u][1] = siz[u] = 1;

	for ( int i = head[u], v; i; i = graph[i].nxt ) {

		if ( ( v = graph[i].to ) ^ fa ) {

			solve ( v, u );

			for ( int j = 1; j <= siz[u] + siz[v]; ++ j ) tmp[j] = 0;

			for ( int j = 0; j <= siz[v]; ++ j ) {

				for ( int k = 1; k <= siz[u]; ++ k ) {

					addeq ( tmp[j + k], 1ll * f[v][j] * f[u][k] % MOD );

				}

			}

			for ( int j = 1; j <= siz[u] + siz[v]; ++ j ) f[u][j] = tmp[j];

			siz[u] += siz[v];

		}

	}

	for ( int i = 2; i <= siz[u]; i += 2 ) addeq ( f[u][0], 1ll * f[u][i] * g[i] % MOD );

	f[u][0] = ( MOD - f[u][0] ) % MOD;

}



int main () {

	scanf ( "%d", &n );

	for ( int i = 1, u, v; i < n; ++ i ) {

		scanf ( "%d %d", &u, &v );

		link ( u, v ), link ( v, u );

	}

	g[0] = 1;

	for ( int i = 2; i <= n; i += 2 ) g[i] = ( i - 1ll ) * g[i - 2] % MOD;

	solve ( 1, 0 );

	printf ( "%d\n", ( MOD - f[1][0] ) % MOD );

	return 0;

}
// Slower C++ solution:
// ===================================

//   author: M_sea

//   website: http://m-sea-blog.com/

// ===================================

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#define re register

using namespace std;



inline int read() {

    int X=0,w=1; char c=getchar();

    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }

    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();

    return X*w;

}



const int N=5000+10;

const int mod=1e9+7;



struct edge { int v,nxt; } e[N<<1];

int head[N];



inline void addEdge(int u,int v) {

    static int e_cnt=0;

    e[++e_cnt]=(edge){v,head[u]},head[u]=e_cnt;

}



int n,sz[N];

int f[N][N],g[N],tmp[N];



inline void dfs(int u,int fa) {

    sz[u]=f[u][1]=1;

    for (re int i=head[u];i;i=e[i].nxt) {

        int v=e[i].v; if (v==fa) continue;

        dfs(v,u);

        for (re int j=1;j<=sz[u]+sz[v];++j) tmp[j]=0;

        for (re int j=1;j<=sz[u];++j)

            for (re int k=0;k<=sz[v];++k)

                tmp[j+k]=(tmp[j+k]+1ll*f[u][j]*f[v][k])%mod;

        sz[u]+=sz[v];

        for (re int j=1;j<=sz[u];++j) f[u][j]=tmp[j];

    }

    for (re int i=2;i<=sz[u];i+=2)

        f[u][0]=(f[u][0]-1ll*f[u][i]*g[i]%mod+mod)%mod;

}



int main() {

    n=read();

    for (re int i=1;i<n;++i) {

        int u=read(),v=read();

        addEdge(u,v),addEdge(v,u);

    }

    g[0]=1;

    for (re int i=2;i<=n;i+=2) g[i]=1ll*g[i-2]*(i-1)%mod;

    dfs(1,0); printf("%d\n",mod-f[1][0]);

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.080276836723996x):
#include <cstdio>



const int MAXN = 5000, MOD = 1e9 + 7;

int n, ecnt, head[MAXN + 5], siz[MAXN + 5];

int g[MAXN + 5], f[MAXN + 5][MAXN + 5];



struct Edge { int to, nxt; } graph[MAXN * 2 + 5];



inline void addeq ( int& a, const int b ) { if ( ( a += b ) >= MOD ) a -= MOD; }



inline void link ( const int s, const int t ) {

	graph[++ ecnt] = { t, head[s] };

	head[s] = ecnt;

}



inline void solve ( const int u, const int fa ) {

	static int tmp[MAXN + 5];

	f[u][1] = siz[u] = 1;

	for ( int i = head[u], v; i; i = graph[i].nxt ) {

		if ( ( v = graph[i].to ) ^ fa ) {

			solve ( v, u );

			for ( int j = 1; j <= siz[u] + siz[v]; ++ j ) tmp[j] = 0;

			for ( int j = 0; j <= siz[v]; ++ j ) {

				for ( int k = 1; k <= siz[u]; ++ k ) {

					addeq ( tmp[j + k], 1ll * f[v][j] * f[u][k] % MOD );

				}

			}

			for ( int j = 1; j <= siz[u] + siz[v]; ++ j ) f[u][j] = tmp[j];

			siz[u] += siz[v];

		}

	}

	for ( int i = 2; i <= siz[u]; i += 2 ) addeq ( f[u][0], 1ll * f[u][i] * g[i] % MOD );

	f[u][0] = ( MOD - f[u][0] ) % MOD;

}



int main () {

	scanf ( "%d", &n );

	for ( int i = 1, u, v; i < n; ++ i ) {

		scanf ( "%d %d", &u, &v );

		link ( u, v ), link ( v, u );

	}

	g[0] = 1;

	for ( int i = 2; i <= n; i += 2 ) g[i] = ( i - 1ll ) * g[i - 2] % MOD;

	solve ( 1, 0 );

	printf ( "%d\n", ( MOD - f[1][0] ) % MOD );

	return 0;

}
// Slower C++ solution:
/*

	边覆盖与不覆盖作为状态非常不好 dp

	可能有多个点覆盖这条边然后就转移不了

	考虑容斥, 这样子我就可以只关注图的某种连通性了

	说到连通性 dp, 常见套路是枚举断不断父边, 然后就可以做了 

*/

#include <bits/stdc++.h>

#define N 5005



using namespace std;



const int mod = 1e9 + 7;



int n;

int head[N], nex[N << 1], to[N << 1], cntE;

int f[N][N], g[N], siz[N], tmp[N];



inline void addE(int u, int v) {

	to[++cntE] = v;

	nex[cntE] = head[u], head[u] = cntE;

}

void dfs(int u, int fa) {

	f[u][siz[u] = 1] = 1;

	for(int i = head[u], v; i; i = nex[i]) {

		v = to[i];

		if(v == fa) continue;

		dfs(v, u);

		memset(tmp, 0, sizeof tmp);

		for(int i = 1; i <= siz[u]; ++i)

			for(int j = 0; j <= siz[v]; ++j)

				tmp[i + j] = (tmp[i + j] + 1LL * f[u][i] * f[v][j]) % mod;

		siz[u] += siz[v];

		for(int i = 1; i <= siz[u]; ++i)

			f[u][i] = tmp[i];

	}

	for(int i = 2; i <= siz[u]; ++i)

		f[u][0] = (f[u][0] - 1LL * f[u][i] * g[i] % mod + mod) % mod;

}



int main() {

	scanf("%d", &n);

	for(int i = 1, u, v; i < n; ++i) {

		scanf("%d %d", &u, &v);

		addE(u, v), addE(v, u);

	}

	

	g[0] = 1;

	for(int i = 2; i <= n; i += 2)

		g[i] = (i - 1LL) * g[i - 2] % mod;

	

	dfs(1, 0);

	

	printf("%d\n", mod - f[1][0]);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.2145753325625055x):
#include <cstdio>



const int MAXN = 5000, MOD = 1e9 + 7;

int n, ecnt, head[MAXN + 5], siz[MAXN + 5];

int g[MAXN + 5], f[MAXN + 5][MAXN + 5];



struct Edge { int to, nxt; } graph[MAXN * 2 + 5];



inline void addeq ( int& a, const int b ) { if ( ( a += b ) >= MOD ) a -= MOD; }



inline void link ( const int s, const int t ) {

	graph[++ ecnt] = { t, head[s] };

	head[s] = ecnt;

}



inline void solve ( const int u, const int fa ) {

	static int tmp[MAXN + 5];

	f[u][1] = siz[u] = 1;

	for ( int i = head[u], v; i; i = graph[i].nxt ) {

		if ( ( v = graph[i].to ) ^ fa ) {

			solve ( v, u );

			for ( int j = 1; j <= siz[u] + siz[v]; ++ j ) tmp[j] = 0;

			for ( int j = 0; j <= siz[v]; ++ j ) {

				for ( int k = 1; k <= siz[u]; ++ k ) {

					addeq ( tmp[j + k], 1ll * f[v][j] * f[u][k] % MOD );

				}

			}

			for ( int j = 1; j <= siz[u] + siz[v]; ++ j ) f[u][j] = tmp[j];

			siz[u] += siz[v];

		}

	}

	for ( int i = 2; i <= siz[u]; i += 2 ) addeq ( f[u][0], 1ll * f[u][i] * g[i] % MOD );

	f[u][0] = ( MOD - f[u][0] ) % MOD;

}



int main () {

	scanf ( "%d", &n );

	for ( int i = 1, u, v; i < n; ++ i ) {

		scanf ( "%d %d", &u, &v );

		link ( u, v ), link ( v, u );

	}

	g[0] = 1;

	for ( int i = 2; i <= n; i += 2 ) g[i] = ( i - 1ll ) * g[i - 2] % MOD;

	solve ( 1, 0 );

	printf ( "%d\n", ( MOD - f[1][0] ) % MOD );

	return 0;

}