stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define int ll

#define mn 100005

#define inf 4444444444444444444

#define mod (ll) 1000000007

#define base 31

#define fi first

#define se second

#define pii pair <int, int>

#define pb push_back

#define mp make_pair



//int t, ntest;

int n, k, ans;

int a[55], dp[55][55][2505];



void input(){

	cin>>n>>k;

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

		cin>>a[i];

	}

}



// i so dau tien, chon j so, tong la t

int d (int i, int j, int t){

	if (j>i) return 0;

	if (j<0 || i<0 || t<0) return 0;

	if (t==0){

		if (j==0) return 1;

		return 0;

	}

	if (j==0 && t!=0) return 0;

	if (dp[i][j][t]<inf) return dp[i][j][t];

	return dp[i][j][t]=d(i-1, j, t)+d(i-1, j-1, t-a[i]);

}



void output(){



}



void solve(){

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

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

			for (int t=1; t<=2500; t++){

				dp[i][j][t]=inf;

			}

		}

	}

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

		ans+=d(n, i, k*i);

	}

	cout<<ans;

}



signed main(){

	ios_base::sync_with_stdio(0);

	cin.tie(0);

//	freopen("test.inp", "r", stdin);

//	freopen("test.out", "w", stdout);

//	cin>>t;

//	for (ntest=1; ntest<=t; ntest++){

		input();

		solve();

		output();

//	}

}



//mtrang_149


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

#include<stdlib.h>

#include<string.h>

typedef long long ll;

ll dp[55][2600];

int v[55];

int main(void)

{

	int N, A;

	ll sum = 0;

	scanf("%d %d", &N, &A);

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

		scanf("%d", &v[i]);

	dp[0][0] = 1;

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

	{

		sum += v[k];

		for (int i = k; i >=1; i--)

			for (int j = sum; j >= v[k]; j--)

				dp[i][j] += dp[i - 1][j - v[k]];

	}

	ll ans = 0;

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

		ans += dp[i][i * A];

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

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define int long long



const int N = 50 + 5, M = N * N;

int n, A, ar[N], dp[2][N][M];



int32_t main() {

	ios::sync_with_stdio(0);

	cin.tie(0);

	

	cin >> n >> A;

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

		cin >> ar[i];

	

	dp[0][0][0] = 1;

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

		int now = (i & 1), prv = (now ^ 1);

		dp[now][0][0] = dp[prv][0][0];

		

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

			for (int x = 0; x < M; x++) {			

				dp[now][j][x] = dp[prv][j][x];

				if (ar[i] <= x)

					dp[now][j][x] += dp[prv][j - 1][x - ar[i]];

			}	

	}

	

	int ans = 0;

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

		int x = A * j;

		ans += dp[n & 1][j][x];

	}

	cout << ans << endl;

}

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

#include<stdlib.h>

#include<string.h>

typedef long long ll;

ll dp[55][2600];

int v[55];

int main(void)

{

	int N, A;

	ll sum = 0;

	scanf("%d %d", &N, &A);

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

		scanf("%d", &v[i]);

	dp[0][0] = 1;

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

	{

		sum += v[k];

		for (int i = k; i >=1; i--)

			for (int j = sum; j >= v[k]; j--)

				dp[i][j] += dp[i - 1][j - v[k]];

	}

	ll ans = 0;

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

		ans += dp[i][i * A];

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

	return 0;

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

using namespace std;



const int MAXN = 55;

long long dp[MAXN][MAXN * MAXN];

int n, A, a[MAXN];



int main() {

	cin >> n >> A;

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

		cin >> a[i];

	dp[0][0] = 1;

	for (int t = 0; t < n; t++)

		for (int j = MAXN * MAXN - 1; j >= 0; j--)

			for (int i = MAXN - 1; i >= 1; i--)

				if (j - a[t] >= 0)

					dp[i][j] += dp[i - 1][j - a[t]];

	long long ans = 0;

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

		ans += dp[i][i * A];

	cout << ans;

}

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

#include<stdlib.h>

#include<string.h>

typedef long long ll;

ll dp[55][2600];

int v[55];

int main(void)

{

	int N, A;

	ll sum = 0;

	scanf("%d %d", &N, &A);

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

		scanf("%d", &v[i]);

	dp[0][0] = 1;

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

	{

		sum += v[k];

		for (int i = k; i >=1; i--)

			for (int j = sum; j >= v[k]; j--)

				dp[i][j] += dp[i - 1][j - v[k]];

	}

	ll ans = 0;

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

		ans += dp[i][i * A];

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

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#include<iostream>

using namespace std;

#define mn 100005

#define FLN "code"

#define endl "\n"

#define int long long

#define fi first

#define se second

#define inf 4444444444444444444

#define mod 1000000009

#define FOR(i, a, b) for (int i=a; i<(b); i++)

#define FOR0(i, a) for (int i=0; i<(a); i++)

#define FOR1(i, a) for (int i=1; i<=(a); i++)

#define codenhanh(); ios_base::sync_with_stdio(0) ,cin.tie(0),cout.tie(0);



int n,m,a[mn];

int dem=0;

vector<int> sum;

signed main()

{

	#ifdef komandocode

	freopen("code.inp", "r", stdin);

	freopen("code.out", "w", stdout);

	#endif

	codenhanh();

	cin>>n;

	cin>>m;

	int dp[60][3000];

	memset(dp, 0, sizeof(dp));

	dp[0][0]=1;

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

		cin>>a[i];

			for(int j=i-1;j>=0;j--)

			{

				for(int p=0;p<=55*j;p++){

					dp[j+1][a[i]+p]+=dp[j][p];

				}	

			}

			}

            



	int ans=0;

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

	{

		ans+=dp[i][i*m];

	}

	cout<<ans;

return 0;

}




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

#include<stdlib.h>

#include<string.h>

typedef long long ll;

ll dp[55][2600];

int v[55];

int main(void)

{

	int N, A;

	ll sum = 0;

	scanf("%d %d", &N, &A);

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

		scanf("%d", &v[i]);

	dp[0][0] = 1;

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

	{

		sum += v[k];

		for (int i = k; i >=1; i--)

			for (int j = sum; j >= v[k]; j--)

				dp[i][j] += dp[i - 1][j - v[k]];

	}

	ll ans = 0;

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

		ans += dp[i][i * A];

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

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

 

using namespace std;

typedef long long ll;

ll ta[55][55][2555];

ll a[55];

 

signed main(){

	//freopen(".INP","r",stdin);

	//freopen(".OUT","w",stdout);

	ios_base::sync_with_stdio(0);

	cin.tie(0);

	cout.tie(0);

	ll n, m;

	cin >> n >> m;

	for (ll i = 0; i < n; i++){

		cin >> a[i];

	}

	ta[0][0][0] = 1;

	for (ll i = 0; i < n; i++){

		for (ll j = 0; j < n; j++){

			for (ll k = 0; k < 2501; k++){

				if (ta[i][j][k]){

					ta[i + 1][j + 1][k + a[i]] += ta[i][j][k];

					ta[i + 1][j][k] += ta[i][j][k];

				}

			}

		}

	}

	ll ans = 0;

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

		ans += ta[n][i][i * m];

	}

	cout << ans;

	return 0;

}

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

#include<stdlib.h>

#include<string.h>

typedef long long ll;

ll dp[55][2600];

int v[55];

int main(void)

{

	int N, A;

	ll sum = 0;

	scanf("%d %d", &N, &A);

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

		scanf("%d", &v[i]);

	dp[0][0] = 1;

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

	{

		sum += v[k];

		for (int i = k; i >=1; i--)

			for (int j = sum; j >= v[k]; j--)

				dp[i][j] += dp[i - 1][j - v[k]];

	}

	ll ans = 0;

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

		ans += dp[i][i * A];

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

	return 0;

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

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const int N=2550;

ll f[6007][57]={0};

int n,a,num[57];

int main()

{

	scanf("%d%d",&n,&a);

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

	{

		int x;

		scanf("%d",&x);

		num[i]=x-a;

	}

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

	{

		for (int j = 55; j < 5057; ++j)

		{

			f[j][i]+=f[j][i-1];

			f[j+num[i]][i]+=f[j][i-1];

		}

		f[N+num[i]][i]++;

	}

	printf("%lld\n", f[N][n]);

	return 0;

}

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

#include<stdlib.h>

#include<string.h>

typedef long long ll;

ll dp[55][2600];

int v[55];

int main(void)

{

	int N, A;

	ll sum = 0;

	scanf("%d %d", &N, &A);

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

		scanf("%d", &v[i]);

	dp[0][0] = 1;

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

	{

		sum += v[k];

		for (int i = k; i >=1; i--)

			for (int j = sum; j >= v[k]; j--)

				dp[i][j] += dp[i - 1][j - v[k]];

	}

	ll ans = 0;

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

		ans += dp[i][i * A];

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

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define inf 0x3f3f3f3f

#define ll long long

const int N=55;

const int mod=1e9+7;

const double eps=1e-8;

const double PI = acos(-1.0);

#define lowbit(x) (x&(-x))

ll dp[N][N*N];

int main()

{

    std::ios::sync_with_stdio(false);

    int n,a;

    ll x;

    cin>>n>>a;

    dp[0][0]=1;

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

    {

        cin>>x;

        for(int j=i-1; j>=0; j--)

        {

            for(int w=0;w<N*N;w++)

            {

                dp[j+1][w+x]+=dp[j][w];

            }

        }

    }

    ll ans=0;

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

    {

        ans+=dp[i][i*a];

    }

    cout<<ans<<endl;

    return 0;

}


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

#include<stdlib.h>

#include<string.h>

typedef long long ll;

ll dp[55][2600];

int v[55];

int main(void)

{

	int N, A;

	ll sum = 0;

	scanf("%d %d", &N, &A);

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

		scanf("%d", &v[i]);

	dp[0][0] = 1;

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

	{

		sum += v[k];

		for (int i = k; i >=1; i--)

			for (int j = sum; j >= v[k]; j--)

				dp[i][j] += dp[i - 1][j - v[k]];

	}

	ll ans = 0;

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

		ans += dp[i][i * A];

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

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define inf 0x3f3f3f3f

#define ll long long

const int N=55;

const int mod=1e9+7;

const double eps=1e-8;

const double PI = acos(-1.0);

#define lowbit(x) (x&(-x))

ll dp[N][N*N];

int main()

{

    std::ios::sync_with_stdio(false);

    int n,a;

    cin>>n>>a;

    dp[0][0]=1;

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

    {

        int x;

        cin>>x;

        for(int j=i-1;j>=0;j--)

        for(int w=0;w<=N*j;w++)

        {

            dp[j+1][w+x]+=dp[j][w];

         //   cout<<j+1<<" "<<w+x<<" "<<dp[j+1][w+x]<<endl;

        }

    }

    ll ans=0;

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

    {

        ans+=dp[i][i*a];

    }

    cout<<ans<<endl;

    return 0;

}


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

#include<stdlib.h>

#include<string.h>

typedef long long ll;

ll dp[55][2600];

int v[55];

int main(void)

{

	int N, A;

	ll sum = 0;

	scanf("%d %d", &N, &A);

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

		scanf("%d", &v[i]);

	dp[0][0] = 1;

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

	{

		sum += v[k];

		for (int i = k; i >=1; i--)

			for (int j = sum; j >= v[k]; j--)

				dp[i][j] += dp[i - 1][j - v[k]];

	}

	ll ans = 0;

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

		ans += dp[i][i * A];

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

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define sci(a) scanf("%d", &a)

#define fto(i, a, b) for (int i = a; i <= b; ++i)

#define fdto(i, a, b) for (int i = a; i >= b; --i)

#define scii(a, b) scanf("%d %d", &a, &b)

#define ll long long

#define ff first

#define ss second

#define vi vector<int>

#define pi pair<int, int>

#define maxN 100005

#define oo 1000000007

#define maxM 2500

#define mp make_pair

#define pb push_back

#define bug(a) cout << #a << "= " << a << endl;

#define bugarr(a, x, y) cout << #a << "[" << x << ", " << y << "]= "; for (int i = x; i <= y; ++i) cout << a[i] << ", "; cout << endl;

#define sz(a) (int)a.size()

#define vii vector<pi>

#define db double

#define forit(var, it) for(__typeof(var.begin()) it = var.begin(); it != var.end(); ++it)



using namespace std;



int n, A, a[100];

ll f[100][10005];



int main() {

   // #ifndef ONLINE_JUDGE

      //  freopen("TakandCards.inp", "r", stdin);

        //freopen("TakandCards.out", "w", stdout);

    //#endif // ONLINE_JUDGE



    scii(n, A);

    fto(i, 1, n) sci(a[i]);

    fto(i, 1, n) a[i]-=A;

    //fto(i, 1, n) cout << a[i] << "\n";

    fto(i, 0, 7000) f[0][i] = 0;

    f[0][2500] = 1;

    fto(i, 1, n) {

        fto(j, -2500, 2500) {

            f[i][j+maxM] = f[i-1][j+maxM];

            if (j - a[i] + maxM >= 0) f[i][j+maxM]+=f[i-1][j-a[i]+maxM];

            //cout << i << " " << j << " " << j-a[i] << " " << f[i][j+maxM] << "\n";

        }

    }

    //cout << f[1][maxM] << "\n";

    cout << f[n][maxM] - 1;



    return 0;

}


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

#include<stdlib.h>

#include<string.h>

typedef long long ll;

ll dp[55][2600];

int v[55];

int main(void)

{

	int N, A;

	ll sum = 0;

	scanf("%d %d", &N, &A);

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

		scanf("%d", &v[i]);

	dp[0][0] = 1;

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

	{

		sum += v[k];

		for (int i = k; i >=1; i--)

			for (int j = sum; j >= v[k]; j--)

				dp[i][j] += dp[i - 1][j - v[k]];

	}

	ll ans = 0;

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

		ans += dp[i][i * A];

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

	return 0;

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

#include<cstring>

using namespace std;

#define ll long long

ll dp[2500][50];

ll a[50];

; int main()

{

	int n, ave;

	cin >> n >> ave;

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

		cin >> a[i];

	memset(dp, 0, sizeof(dp));

	dp[0][0] = 1;

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

		for (int j = n * 50; j >= a[i]; j--)

			for (int k = 1; k <= n; k++)

				if (dp[j - a[i]][k - 1])

					dp[j][k] += dp[j - a[i]][k - 1];

	ll ans = 0;

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

		ans += dp[i * ave][i];

	cout << ans << endl;

	return 0;

}

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

#include<stdlib.h>

#include<string.h>

typedef long long ll;

ll dp[55][2600];

int v[55];

int main(void)

{

	int N, A;

	ll sum = 0;

	scanf("%d %d", &N, &A);

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

		scanf("%d", &v[i]);

	dp[0][0] = 1;

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

	{

		sum += v[k];

		for (int i = k; i >=1; i--)

			for (int j = sum; j >= v[k]; j--)

				dp[i][j] += dp[i - 1][j - v[k]];

	}

	ll ans = 0;

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

		ans += dp[i][i * A];

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

	return 0;

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

#include<cstdio>

typedef long long ll;

using namespace std;



int a[55];

int sum[55];

ll dp[55][2505];



int main()

{

    int n,A;

    scanf("%d%d",&n,&A);

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

	{

	scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i];

	}

    dp[0][0]=1;

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

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

            for(int j=sum[k];j>=a[k];j--){

                dp[i][j]+=dp[i-1][j-a[k]];

            }

        }

    }

    ll ans=0;

    for(int i=1;i<=n;i++) ans+=dp[i][i*A];

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

    return 0;

}

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

#include<stdlib.h>

#include<string.h>

typedef long long ll;

ll dp[55][2600];

int v[55];

int main(void)

{

	int N, A;

	ll sum = 0;

	scanf("%d %d", &N, &A);

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

		scanf("%d", &v[i]);

	dp[0][0] = 1;

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

	{

		sum += v[k];

		for (int i = k; i >=1; i--)

			for (int j = sum; j >= v[k]; j--)

				dp[i][j] += dp[i - 1][j - v[k]];

	}

	ll ans = 0;

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

		ans += dp[i][i * A];

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

	return 0;

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

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#include <iomanip>

using namespace std;

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

#define repd(i,x,n) for(int i=x;i<=n;i++)

typedef long long ll;

ll dp[55][55 * 55];

int k;

int n;

int main()

{

    cin >> n >> k;

    int x;

    dp[0][0] = 1ll;

    repd(i, 1, n)

    {

        cin >> x;

        for (int j = i - 1; j >= 0; j--)

        {

            for (int w = 0; w <= 55 * j; w++)

            {

                dp[j + 1][w + x] += dp[j][w];

            }

        }

    }

    ll ans = 0ll;

    repd(i, 1, n)

    {

        ans += dp[i][i * k];

    }

    cout << ans << endl;

    return 0;

}

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

#include<stdlib.h>

#include<string.h>

typedef long long ll;

ll dp[55][2600];

int v[55];

int main(void)

{

	int N, A;

	ll sum = 0;

	scanf("%d %d", &N, &A);

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

		scanf("%d", &v[i]);

	dp[0][0] = 1;

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

	{

		sum += v[k];

		for (int i = k; i >=1; i--)

			for (int j = sum; j >= v[k]; j--)

				dp[i][j] += dp[i - 1][j - v[k]];

	}

	ll ans = 0;

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

		ans += dp[i][i * A];

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

	return 0;

}
// Slower C++ solution:
/*

    f[x]表示以x为根的子树中，先把x染成白之后对方下一步是否会在x子树中操作 

    g[x]表示以x为根的子树中，先手是否能获得胜利。

    

    当我们枚举致胜节点为root时，先手能赢当且仅当g[root]=1. 

	

	初始化(对于单点)：

	     g[x]=1;

	     f[x]=0;

	

	

	转移：

	    1.f[x]等于所有儿子的g的位或

		 

		 这个不难理解，因为只要有一个儿子的g为1的话，我们先把x染白，

		 对方一定会在g为1的这个子树中操作，不然就输了。

		 

		2.g[x]等于所有儿子的f的位与

		

		 这个也不难理解，因为只有所有儿子的f都为1了，我们才可以依次把每个儿子染白

		 最后依然有先手优势来染x，然后就赢了hhhh

	

	考虑上述算法仅适用于根固定的情况 ，我们可以把它扩展一下，

	第一遍dfs预处理以某个节点为根的函数值，

	第二遍dfs在每个节点O(1)计算出函数值。 

*/

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<vector>

#define ll long long

#define maxn 100005

#define pb push_back

using namespace std;

vector<int> son[maxn];

int n,m,g[maxn];

int f[maxn];

bool win=0;



void dfs1(int x,int fa){

	int sz=son[x].size()-1,to;

	f[x]=0,g[x]=1;

	

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

		to=son[x][i];

		if(to==fa) continue;;

		dfs1(to,x);

		f[x]|=g[to],g[x]&=f[to];

	}

}



void dfs2(int x,int fa,int fa_f,int fa_g){

	int sz=son[x].size()-1,to;

	int hzf[sz+2],hzg[sz+2];

	hzf[sz+1]=1,hzg[sz+1]=0;

	

	if(g[x]&fa_f) win=1;

	

	for(int i=sz;i>=0;i--){

		hzf[i]=hzf[i+1];

		hzg[i]=hzg[i+1];

		to=son[x][i];

		if(to==fa) continue;

		

		hzf[i]&=f[to];

		hzg[i]|=g[to];

	}

	

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

		to=son[x][i];

		if(to==fa) continue;

		

		dfs2(to,x,fa_g|hzg[i+1],fa_f&hzf[i+1]);

		fa_g|=g[to];

		fa_f&=f[to];

	}

}



int main(){

	int uu,vv;

	scanf("%d",&n);

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

		scanf("%d%d",&uu,&vv);

		son[uu].pb(vv);

		son[vv].pb(uu);

	}

	

	dfs1(1,0);

	dfs2(1,0,1,0);

	

	if(win) puts("First");

	else puts("Second");

	

	return 0;

}

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

using namespace std;

struct E{int v,next;}g[200005];

int n,h[100005],t,ans;

void ins(int u,int v){g[++t].v=v,g[t].next=h[u],h[u]=t;}

inline int read(){

    int x=0,f=1;char ch=getchar();

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

    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

    return x*f;

}

int dfs(int now,int last){

	int tot=0;

	for(int i=h[now];i;i=g[i].next) if(g[i].v!=last) tot+=dfs(g[i].v,now);

	if(tot>=2){puts("First");exit(0);}

	if(tot==0) return 1;

	return 0;

}

int main(){

	int u,v;

	n=read();

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

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

		ins(u,v),ins(v,u);

	}

	ans=dfs(1,-1);

	if(ans) puts("First");

	else puts("Second");

}
// Slower C++ solution:
#include <bits/stdc++.h>

typedef long long int ll;

typedef long double ld;

#define pb push_back

#define pii pair < int , int >

#define F first

#define S second

#define endl '\n'

#define int long long

#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")

#define kill(x) return cout<<x<<'\n', 0;

using namespace std;

const int N=2e5+100;

vector <int> g[N];

ll vis[N];

void dfs(ll v,ll p){

    for (auto u : g[v]){

        if (u==p) continue;

        dfs(u,v);

        if (vis[u]==0 && vis[v]==0){

            vis[u]=1;

            vis[v]=1;

        }

    }

}

int32_t main(){

    sync;

    ll n;

    cin >> n;

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

        ll u,v;

        cin >> u >> v;

        g[u].pb(v);

        g[v].pb(u);

    }

    dfs(1,1);

    for (int i=1;i<=n;i++) if (vis[i]==0) kill("First");

    kill("Second");

}

// Faster C++ solution for the same problem (measured speedup: 1.8113623425006964x):
//Sasayego! Sasayego! Shinzou wo Sasageyo!



#include <iostream>

#include <iomanip>

#include <algorithm>

#include <cmath>

#include <ctime>

#include <cstring>

#include <vector>

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <numeric>

#include <bitset>

#include <ctime>

#define debug(x)  cerr << #x << " = " << x << endl

#define lid (id << 1)

#define rid (lid ^ 1)

using namespace std;

typedef long long ll;

typedef long double ld;

typedef pair <ll, ll> pll;

typedef pair <int, int> pii;



const int maxN = 1e5 + 5;

const ll INF = 1e18;

const ll MOD = 1e9 + 7;



int arumin[maxN];

vector <int> G[maxN];



int LEVI(int v, int p = -1){

	int cnt[3] = {0, 0, 0};

	for (int u : G[v]){

		if (u == p)

			continue;

		cnt[LEVI(u, v)]++;

	}

	if (cnt[0] > 0 || cnt[2] > 1)

		return arumin[v] = 0;

	return arumin[v] = 2 - cnt[2];

}



int main(){

	time_t START = clock();

	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int n; scanf("%d", &n);

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

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

		G[u].push_back(v);

		G[v].push_back(u);

	}

	printf(LEVI(1) & 1 ? "Second\n" : "First\n");

	time_t FINISH = clock();

	cerr << "Execution time: " << (ld)(FINISH - START) / CLOCKS_PER_SEC * 1000.0 << " milliseconds.\n";

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define N 200010

using namespace std;



int n, q[N], l, r, deg[N];

bool vis[N], inqueue[N];

vector<int> edge[N];

int main() {

	scanf("%d", &n);

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

		int x, y;

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

		edge[x].push_back(y);

		edge[y].push_back(x);

		++deg[x]; ++deg[y];

	}

	

	l = r = 0;

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

		if (deg[i] == 1) {

			q[++r] = i;

			inqueue[i] = 1;

		}

	}



	while (l < r) {

		int nq = -1;

		int u = q[l++];

		for (int j = 0; j < edge[u].size(); ++j) {

			int v = edge[u][j];

			if (!vis[v]) {

				nq = v;

				vis[v] = 1;

				vis[u] = 1;

				break;

			}

		}

		

		if (nq == -1) continue;

		for (int i = 0; i < edge[nq].size(); ++i) {

			int v = edge[nq][i];

			if (!inqueue[v] && --deg[v] == 1) {

				q[++r] = v;

				inqueue[v] = 1;

			}

		}

	}

	

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

		if (!vis[i]) {

			puts("First");

			return 0;

		}

	}

	puts("Second");

}

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

#define MAXN 100006

#include<queue>

#include<vector>

#include<algorithm>

using namespace std;

vector<int> road[MAXN];

int n,u,v,du[MAXN],vis[MAXN];

queue<int> q;

int main()

{

	//freopen("blackwhite.in","r",stdin);

	//freopen("blackwhite.out","w",stdout);

	scanf("%d",&n);

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

	{

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

		road[u].push_back(v);

		road[v].push_back(u);

		du[u]++;

		du[v]++;

	}

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

		if(du[i]==1) q.push(i);

	while(!q.empty())

	{

		int now=q.front();

		q.pop();

		if(vis[now]) continue;

		if(du[now]==1)

		{

			for(int i=0;i<(int)road[now].size();i++)

			{

				int nex=road[now][i];

				if(!vis[nex])

				{

					vis[nex]=vis[now]=1;

					for(int j=0;j<(int)road[nex].size();j++)

					{

						int nnex=road[nex][j];

						if(vis[nnex]) continue;

						du[nnex]--;

						if(du[nnex]==1) q.push(nnex);

					}

					break;

				}

			}

		}

	}

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

		if(!vis[i])

		{

			printf("First");

			return 0;

		}

	printf("Second");

}