CodeEff/ECCO huggingface dataset:
# Original solution
n,a,*x=list(map(int,open(0).read().split()));dp={0:1}
for i in x:
	for k,v in set(dp.items()):
		dp[i+k-a]=dp.get(i+k-a,0)+v
print((dp[0]-1))

# Optimized solution
n,a,*X=list(map(int,open(0).read().split()))
y=[a-x for x in X]
dp={0:1}
for i in y:
	for k,v in set(dp.items()):
		dp[i+k]=dp.get(i+k,0)+v
print((dp[0]-1))
# Original solution
n,a=list(map(int,input().split()))
y=[a-int(x) for x in input().split()]
dp={0:1}
for i in y:
	for k,v in list(dp.items()):
		dp[i+k]=dp.get(i+k,0)+v
print((dp[0]-1))

# Optimized solution
def main():
	n,a=list(map(int,input().split()))
	y=[a-int(x) for x in input().split()]
	dp={0:1}
	for i in y:
		for k,v in list(dp.items()):
			dp[i+k]=dp.get(i+k,0)+v
	print((dp[0]-1))
if __name__=="__main__":
	main()
# Original solution
def solve():
  ans = 0
  N, A = list(map(int, input().split()))
  X = list(map(int, input().split()))
  x = sum(X)
  dp = [[[0]*2550 for _ in range(N+1)] for _ in range(N+1)]
  dp[0][0][0] = 1
  for i in range(N):
    for j in range(i+1):
      for k in range(x):
        dp[i+1][j][k] += dp[i][j][k]
        dp[i+1][j+1][k+X[i]] += dp[i][j][k]
  for j in range(1,N+1):
    ans += dp[-1][j][j*A]
  return ans
print((solve()))

# Optimized solution
N, A = list(map(int, input().split()))
X = list([int(x)-A for x in input().split()])
dp = [0]*10000
dp[0] = 1
for i in range(N):
  new_dp = dp[:]
  for j in range(-3000,3000):
    if dp[j]>0:
      new_dp[j+X[i]] += dp[j]
  dp = new_dp
print((dp[0]-1))
# Original solution
N,A = list(map(int,input().split()))
X = list(map(int,input().split()))
 
dp = [[[0 for k in range(2501)] for j in range(N+1)] for i in range(N+1)]
 
for i in range(1,N+1):
    x = X[i-1]
    dp[i][1][x] += 1
    for j in range(1,i+1):
        for k in range(1,2501):
            if k-x > 0:
                dp[i][j][k] += dp[i-1][j-1][k-x] + dp[i-1][j][k]
            else:
                dp[i][j][k] += dp[i-1][j][k]
 
ans = 0
 
for j in range(1,N+1):
    ans += dp[N][j][j*A]
print(ans)

# Optimized solution
N,A = list(map(int,input().split()))
X = list(map(int,input().split()))

for i in range(N):
    X[i] -= A

from collections import defaultdict

counter = defaultdict(int)
counter[0] = 1

for x in X:
    copy = dict(counter)
    for k,v in list(copy.items()):
        counter[k+x] += v

print((counter[0]-1))
# Original solution
from collections import Counter
N,A = list(map(int,input().split()))
X = list(map(int,input().split()))

dp = [Counter() for i in range(N+1)]
dp[0][0] = 1

for i,x in enumerate(X):
    for j in range(i,-1,-1):
        for k,v in list(dp[j].items()):
            dp[j+1][k+x] += v

ans = 0
for i in range(1,N+1):
    ans += dp[i][A*i]
print(ans)

# Optimized solution
N,A = list(map(int,input().split()))
X = list(map(int,input().split()))

from collections import defaultdict
dp = [defaultdict(lambda: 0) for _ in range(N+1)]
dp[0][0] = 1
for i,x in enumerate(X):
    for j in range(i,-1,-1):
        for k,v in list(dp[j].items()):
            dp[j+1][k+x] += v

ans = 0
for i in range(1,N+1):
    ans += dp[i][i*A]
print(ans)
# Original solution
n, a = list(map(int, input().split()))
xlist = list(map(int, input().split()))

j = n
k = n
t = n * a



dp = [[[0 for t in range(t + 1)] for k in range(k + 1)] for j in range(j + 1)]

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

# for d in dp:
#     print(d)
# print(dp[1][1][15])

for ji in range(1, j + 1):
    for ki in range(0, ji + 1):
        for ti in range(0, t + 1):
            # print('now', ji, ki, ti)
            if ji == 0 and ki == 0 and ti == 0:
                # print('branch 1')
                dp[ji][ki][ti] = 1
            elif ji >= 1 and ti < xlist[ji - 1]:
                dp[ji][ki][ti] = dp[ji - 1][ki][ti]
                # print('branch 2')
            elif ji >= 1 and ki >= 1 and ti >= xlist[ji - 1]:
                # print('branch 3', ji - 1)
                dp[ji][ki][ti] = dp[ji - 1][ki][ti] + dp[ji - 1][ki - 1][ti - xlist[ji - 1]]
            # print(dp[ji][ki][ti])

count = 0
for i in range(1, k + 1):
    count += dp[j][i][i*a]

print(count)

# Optimized solution
n, a = list(map(int, input().split()))
xlist = list(map(int, input().split()))

j = n
k = n
t = n * a
maxv = max(a, max(xlist))


dp = [[[0 for t in range(n*maxv + 1)] for k in range(k + 1)] for j in range(j + 1)]

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

# for d in dp:
#     print(d)
# print(dp[1][1][15])

for ji in range(0, j + 1):
    for ki in range(0, ji + 1):
        for ti in range(0, ki * maxv + 1):
            # print('now', ji, ki, ti)
            if ji == 0 and ki == 0 and ti == 0:
                # print('branch 1')
                dp[ji][ki][ti] = 1
            elif ji >= 1 and ti < xlist[ji - 1]:
                dp[ji][ki][ti] = dp[ji - 1][ki][ti]
                # print('branch 2')
            elif ji >= 1 and ki >= 1 and ti >= xlist[ji - 1]:
                # print('branch 3', ji - 1)
                dp[ji][ki][ti] = dp[ji - 1][ki][ti] + dp[ji - 1][ki - 1][ti - xlist[ji - 1]]
            # print(dp[ji][ki][ti])

count = 0
for i in range(1, k + 1):
    count += dp[j][i][i*a]

print(count)
# Original solution
import sys
from collections import defaultdict


def main():
    N, A, *xlst = list(map(int, sys.stdin.read().split()))
    x_p = []
    x_n = []
    x_z = 0
    xlst.sort()
    for i in xlst:
        if A < i:
            x_p.append(i - A)
        elif i < A:
            x_n.append(A - i)
        else:
            x_z += 1

    x_p_sum = defaultdict(int, {0: 1})
    x_n_sum = defaultdict(int, {0: 1})
    for i in range(len(x_p)):
        for j in sorted(x_p_sum, reverse=1):
            x_p_sum[j + x_p[i]] += x_p_sum[j]

    for i in range(len(x_n)):
        for j in sorted(x_n_sum, reverse=1):
            x_n_sum[j + x_n[i]] += x_n_sum[j]

    res = 0
    for i in x_n_sum:
        if i in x_p_sum:
            res += (x_n_sum[i] * x_p_sum[i])
    res *= 1 << x_z
    res -= 1
    print(res)


if __name__ == '__main__':
    main()

# Optimized solution
import sys
from collections import defaultdict


def main():
    N, A, *xlst = list(map(int, sys.stdin.read().split()))
    x_p = []
    x_n = []
    x_z = 0
    for i in xlst:
        if A < i:
            x_p.append(i - A)
        elif i < A:
            x_n.append(A - i)
        else:
            x_z += 1
    x_p.sort(), x_n.sort()

    x_p_sum = defaultdict(int, {0: 1})
    x_n_sum = defaultdict(int, {0: 1})
    for i in range(len(x_p)):
        for j in sorted(x_p_sum, reverse=1):
            x_p_sum[j + x_p[i]] += x_p_sum[j]

    for i in range(len(x_n)):
        for j in sorted(x_n_sum, reverse=1):
            x_n_sum[j + x_n[i]] += x_n_sum[j]

    res = 0
    for i in x_p_sum:
        if i in x_n_sum:
            res += (x_n_sum[i] * x_p_sum[i])
    res *= 1 << x_z
    res -= 1
    print(res)


if __name__ == '__main__':
    main()
# Original solution
n, a = list(map(int, input().split()))
xs = list(map(int, input().split()))

na = n*a
DP = [[0]*(na+1) for i in range(n+1)]
DP[0][0] = 1

for _ in range(n):
    x = xs[_]
    next = [[0]*(na+1) for i in range(n+1)]
    for i in range(n):
        for j in range(na+1):
            # xを使わないとき
            next[i][j] += DP[i][j]
            if j+x <= na:
                next[i+1][j+x] += DP[i][j]
    DP = next

# i枚使ったとき合計がi*aである場合の数
ans = 0
for i in range(1,n+1):
    ans += DP[i][i*a]
print(ans)

# Optimized solution
n, a = list(map(int, input().split()))
xs = list(map(int, input().split()))

na = n*a

DP = [[0]*(na+1) for i in range(n+1)]
DP[0][0] = 1

for _ in range(n):
    x = xs[_]
    next = [[0]*(na+1) for i in range(n+1)]
    for i in range(_+1):
        for j in range(na+1):
            # xを使わないとき
            next[i][j] += DP[i][j]
            if j+x <= na:
                next[i+1][j+x] += DP[i][j]
    DP = next

# i枚使ったとき合計がi*aである場合の数
ans = 0
for i in range(1,n+1):
    ans += DP[i][i*a]
print(ans)
# Original solution
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# ありえる平均は1..50のいずれか

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

N, A = list(map(int, input().split()))
Xs = list(sorted(map(int, input().split())))

lower = []
same = 0
upper = []
for x in Xs:
    if x < A:
        lower.append(A - x)
    elif x == A:
        same += 1
    else:
        upper.append(x - A)

def make_counter(nums):
    counter = Counter({0: 1})
    for n in nums:
        # 使う場合、使わない場合
        new_counter = Counter()
        for k, v in list(counter.items()):
            new_counter[k] += v
            new_counter[k + n] += v
        counter = new_counter
    return counter

lower_counter = make_counter(lower)
upper_counter = make_counter(upper)

ans = 0
for lk, lv in list(lower_counter.items()):
    # (i) Aに等しい数だけ使う
    if lk == 0:
        # ひとつも選ばれない場合を除くために-1
        ans += 2 ** same - 1
    # (ii) それ以外
    else:
        # Aより小さい数たちと、Aより大きい数たちとの集合の平均がちょうどA
        if lk in upper_counter:
            ans += (2 ** same) * lv * upper_counter[lk]

print(ans)


    
    


# Optimized solution
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 終了後に自力AC 
#
# カードを「Aより小さい」「Aに等しい」「Aより大きい」に分ける。
#
# 「Aより小さい」カードで「和がSになる組み合わせの数」は容易に計算できる。
# 「Aより大きい」カードで「和がTになる組み合わせの数」も計算できる。
#
# あとはこれらを組み合わせるだけ

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

N, A = list(map(int, input().split()))
Xs = list(sorted(map(int, input().split())))

lower = []
same = 0
upper = []
for x in Xs:
    if x < A:
        lower.append(A - x)
    elif x == A:
        same += 1
    else:
        upper.append(x - A)

def make_counter(nums):
    counter = Counter({0: 1})
    for n in nums:
        new_counter = Counter()
        for k, v in list(counter.items()):
            # 使う場合、使わない場合それぞれの場合の数を増やす
            new_counter[k] += v
            new_counter[k + n] += v
        counter = new_counter
    return counter

lower_counter = make_counter(lower)
upper_counter = make_counter(upper)

ans = 0
for lk, lv in list(lower_counter.items()):
    # (i) Aに等しい数だけ使う
    if lk == 0:
        # ひとつも選ばれない場合を除くために-1
        ans += 2 ** same - 1
    # (ii) それ以外
    else:
        # Aより小さい数たちと、Aより大きい数たちとの集合の平均がちょうどA
        if lk in upper_counter:
            ans += (2 ** same) * lv * upper_counter[lk]

print(ans)
# Original solution
n, a = list(map(int, input().split()))
x = list(map(int, input().split()))

# import numpy as np
# dp = np.full((n + 1, n + 1, n * max(x + [a]) + 1), None).tolist()
#
def full(shape, value):
    if not shape:
        return value
    return [full(shape[1:], value) for _ in range(shape[0])]
dp = full((n + 1, n + 1, n * max(x + [a]) + 1), None)

def dfs(j=n, k=n, s=n * max(x)):
    if dp[j][k][s] is not None:
        return dp[j][k][s]
    if j == k == s == 0:
        dp[0][0][0] = 1
        return 1
    result = 0
    if j >= 1:
        if x[j - 1] > s:
            result = dfs(j - 1, k, s)
        elif k >= 1:
            result = dfs(j - 1, k, s) + dfs(j - 1, k - 1, s - x[j - 1])
    dp[j][k][s] = result
    return result

print((sum(dfs(n, k, k * a) for k in range(1, n + 1))))


# Optimized solution
n, a = list(map(int, input().split()))
x = list(map(int, input().split()))

for i in range(n):
    x[i] -= a


def full(shape, value):
    if not shape:
        return value
    return [full(shape[1:], value) for _ in range(shape[0])]

minus_cnt = 0
plus_cnt = 0
for v in x:
    if v < 0:
        minus_cnt -= v
    elif v > 0:
        plus_cnt += v

dp = full((n + 1, minus_cnt + plus_cnt + 5, n + 1), None)
def dfs(k, s=0, depth=n - 1): # ret -> pattern count
    if dp[k][s][depth] is not None:
        return dp[k][s][depth]
    if k == 0:
        if s == 0:
            result = 1
        else:
            result = 0
        dp[k][s][depth] = result
        return result
    if depth == -1:
        dp[k][s][depth] = 0
        return 0
    result = dfs(k - 1, s + x[depth], depth - 1) + dfs(k, s, depth - 1)
    dp[k][s][depth] = result
    return result

result = 0
for i in range(1, n + 1):
    result += dfs(i)
print(result)
# Original solution
N, A = list(map(int, input().split()))
x = sorted(map(int, input().split()))

def solve(n):
    mem = {}
    def rec(i, a, d):
        if (i, a, d) in mem:
            return mem[(i, a, d)]
        if i >= N:
            return 0
        if a < x[i]:
            return 0
        if d > n:
            return 0
        if x[i] == a and d == n-1:
            mem[(i, a, d)] = rec(i+1, a, d) + 1
        else:
            mem[(i, a, d)] = rec(i+1, a, d) + rec(i+1, a-x[i], d+1)
        return mem[(i, a, d)]
    return rec(0, n*A, 0)

s = 0
for i in range(1, N+1):
    s += solve(i)
print(s)


# Optimized solution
N, A = list(map(int, input().split()))
a = sorted([int(x)-A for x in input().split()])
mem = {}

def rec(p, acm):
    if (p, acm) in mem:
        return mem[(p, acm)]
    if p >= N:
        return 0
    if a[p] > 0 and acm > 0:
        return 0
    mem[(p, acm)] = rec(p+1, acm+a[p]) + rec(p+1, acm)
    if acm+a[p] == 0:
        mem[(p, acm)] += 1
    return mem[(p, acm)]

print(rec(0, 0))
# Original solution
import itertools
n,a = list(map(int,input().split()))
x = list(map(int,input().split()))

xa = []
xb = []
count = 0
for i in x:
    if i > a:
        xa.append(i-a)
    elif i < a:
        xb.append(i-a)
    else:
        count += 1
ans = 0
if len(xa) == 0 or len(xb) == 0:
    print((2**count-1))
else:
    for i in range(1,len(xa)+1):
        for j in range(1,len(xb)+1):
            for k in itertools.combinations(xa,i):
                for l in itertools.combinations(xb,j):
                    if sum(k)+sum(l) == 0:
                        ans += 1
    if ans == 0:
        print((0))
    elif count == 0:
        print(ans)
    else:
        print(((ans+1)*2**count-count))

# Optimized solution
n,a = list(map(int, input().split()))
x = list(map(int,input().split()))
x = [i-a for i in x]

d = {}
d[0] = 1
for i in x:
    for j,k in list(d.items()):
        d[j+i] = d.get(j+i,0)+k
print((d[0]-1))
# Original solution
n,a=list(map(int,input().split()))
l=list(map(int,input().split()))
dp=[0]*5300
dp[l[0]-a]=1

for x in l[1:]:
  b=x-a
  if b>=0:
    for i in range(2500,-2501,-1):
      dp[i+b]+=dp[i]
  else:
    for i in range(-2500,2501):
      dp[i+b]+=dp[i]
  dp[b]+=1
print((dp[0]))

# Optimized solution
n,a=list(map(int,input().split()))
from collections import defaultdict
dp=defaultdict(int)
dp[0]=1
for i in map(int,input().split()):
    i-=a

    for k in sorted(list(dp.keys()),reverse=(i>=0)):
        dp[k+i]+=dp[k]
print((dp[0]-1))
# Original solution
def makelist(n,m,p):
    return [[[0 for k in range(p)]for i in range(m)]for j in range(n)]

n,a = list(map(int,input().split()))
x = list(map(int,input().split()))
X = max(x)
X = max(X,a)

dp = makelist(n+1,n+1,n*X+1)
dp[0][0][0] = 1
for j in range(n+1):
    for k in range(n+1):
        for s in range(n*X+1):
            if j*k > 0 and s >= x[j-1]:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
            elif j >= 1 and s < x[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
ans = 0
for k in range(1,n+1):
    ans += dp[n][k][k*a]
print(ans)

# Optimized solution
def makelist2(n,m):
    return[[0 for k in range(m)]for i in range(n)]

n,a = list(map(int,input().split()))
x = list(map(int,input().split()))
X = max(x)
X = max(X,a)
b=[]
for i in range(n):
    b.append(x[i]-a)


dp =makelist2(n+1,2*n*X+1)
dp[0][n*X] = 1
for j in range(n+1):
    for t in range(2*n*X+1):
        if j>=1 and (t-b[j-1] < 0 or t-b[j-1]>2*n*X):
            dp[j][t] = dp[j-1][t]
        elif j>= 1:
            dp[j][t] = dp[j-1][t] + dp[j-1][t-b[j-1]]
print((dp[n][n*X]-1))
# Original solution
"""
普通に数え上げDPで行けそう
dp[i][j][k] ->　カードをi枚使う/j種類目のカードまで見る/カードの数字の合計がkになる
j種類目のカードを使う場合：
dp[i][j][k] += dp[i-1][j-1][k-x]
j種類目のカードを使わない場合：
dp[i][j][k] += dp[i][j-1][k]

という風に計算していって、最終的に各iごとにk/i=Aとなるようなkを見出して、dp[i][-1][k]をanswerとして加算する。
"""
N,A = list(map(int,input().split()))
X = list(map(int,input().split()))
sumX = sum(X)
dp = [[[0]*(sumX+1) for _ in range(N+1)]for _ in range(N+1)]
for j in range(N+1):
    dp[0][j][0] = 1
for i in range(1,N+1):
    for j in range(1,N+1):
        x = X[j-1]
        for k in range(1,sumX+1):
            dp[i][j][k] += dp[i][j-1][k]
            if k-x >= 0:
                dp[i][j][k] += dp[i-1][j-1][k-x]
ans = 0
for i in range(1,N+1):
    target = A*i
    if target <= sumX:
        ans += dp[i][-1][target]

print(ans)



# Optimized solution
N,A = list(map(int,input().split()))
X = list(map(int,input().split()))
Y = [x-A for x in X]
t = sum(X)
dp = [[0]*(t*2+1) for _ in range(N+1)]
#dp[i][j] -> i枚目まで見る。合計をj-tにするパターン数
#i枚目を使う場合 -> dp[i][j] += dp[i-1][j-Yi]
#i枚目を使わない場合 -> dp[i][j] += dp[i-1][j]
dp[0][t] = 1

for i in range(1,N+1):
    y = Y[i-1]
    for j in range(t*2+1):
        if 0 <= j-y <= t*2:
            dp[i][j] += dp[i-1][j-y]
        dp[i][j] += dp[i-1][j]

print((dp[-1][t]-1))
# Original solution
N,A = list(map(int,input().split()))
X = list(map(int,input().split()))
X = [x-A for x in X]
dp = [[0]*(5001) for _ in range(N+1)]
dp[0][2500] = 1
for i in range(1,N+1):
    x = X[i-1]
    for j in range(5001):
        dp[i][j] += dp[i-1][j]
        if 0<=j-x<5001:
            dp[i][j] += dp[i-1][j-x]

print((dp[-1][2500]-1))



# Optimized solution
N,A = list(map(int,input().split()))
X = list(map(int,input().split()))
X = [A-x for x in X]
dp = [[0]*(5001) for _ in range(N+1)]
dp[0][2500] = 1
for i in range(1,N+1):
    x = X[i-1]
    for j in range(5001):
        if 0<=j-x<5001:
            dp[i][j] = dp[i-1][j-x]+dp[i-1][j]
        else:
            dp[i][j] = dp[i-1][j]

print((dp[-1][2500]-1))
# Original solution
n,a=list(map(int,input().split()))
X=list(map(int,input().split()))
dp=[[[0]*52 for _ in range(2505)] for _ in range(52)]
ans=0
dp[0][0][0]=1
for i in range(n):
    for j in range(52+50*i):
        for k in range(51):
            ni=i+1
            nj=j+X[i]
            nk=k+1
            dp[ni][nj][nk]+=dp[i][j][k]
            dp[ni][j][k]+=dp[i][j][k]
ans=0
for i in range(1,n+1):
    ans+=dp[n][i*a][i]
print(ans)

# Optimized solution
n,a=list(map(int,input().split()))
X=list(map(int,input().split()))
dp=[[[0]*55 for _ in range(2555)] for _ in range(55)]
ans=0
dp[0][0][0]=1
for i in range(n):
    for j in range(52+50*i):
        for k in range(n):
            ni=i+1
            nj=j+X[i]
            nk=k+1
            dp[ni][nj][nk]+=dp[i][j][k]
            dp[ni][j][k]+=dp[i][j][k]
ans=0
for i in range(1,n+1):
    ans+=dp[n][i*a][i]
print(ans)
# Original solution
N = list(map(int,input().split()))[0]
lis = [[] for i in range(N)]

for a_i,b_i in [ list(map(int,input().split())) for _ in range(N-1) ]:
	lis[a_i-1].append(b_i-1)
	lis[b_i-1].append(a_i-1)

flag = False
while True:
	flag = False

	sumsum = 0
	for x in lis:
		sumsum += sum(x)
	if sumsum == 0:
		print("Second")
		quit()

	for i in range(len(lis)):

		if flag:
			break

		if len(lis[i]) == 1:
			b = lis[i][0]
			lis[i].remove(b)
			lis[b].remove(i)
			for c in lis[b]:
				lis[c].remove(b)
				if len(lis[c]) == 0:
					print("First")
					quit()
			lis[b] = []
			flag = True

# Optimized solution
N = list(map(int,input().split()))[0]
lis = [[] for i in range(N)]

for a_i,b_i in [ list(map(int,input().split())) for _ in range(N-1) ]:
	lis[a_i-1].append(b_i-1)
	lis[b_i-1].append(a_i-1)

while True:

	sumsum = 0
	for x in lis:
		sumsum += sum(x)
	if sumsum == 0:
		print("Second")
		quit()

	for i in range(len(lis)):

		if len(lis[i]) == 1:
			b = lis[i][0]
			lis[i].remove(b)
			lis[b].remove(i)
			for c in lis[b]:
				lis[c].remove(b)
				if len(lis[c]) == 0:
					print("First")
					quit()
			lis[b] = []
# Original solution
import collections
class Dinic:
    def __init__(self, vnum):
        self.edge = [[] for i in range(vnum)]
        self.n = vnum
        self.inf = float('inf')
    def addedge(self, st, en, c):
        self.edge[st].append([en, c, len(self.edge[en])])
        self.edge[en].append([st, 0, len(self.edge[st])-1])
    def bfs(self, vst):
        dist = [-1]*self.n
        dist[vst] = 0
        Q = collections.deque([vst])
        while Q:
            nv = Q.popleft()
            for vt, c, r in self.edge[nv]:
                if dist[vt] == -1 and c > 0:
                    dist[vt] = dist[nv] + 1
                    Q.append(vt)
        self.dist = dist
    def dfs(self, nv, en, nf):
        nextv = self.nextv
        if nv == en:
            return nf
        dist = self.dist
        ist = nextv[nv]
        for i, (vt, c, r) in enumerate(self.edge[nv][ist:], ist):
            if dist[nv] < dist[vt] and c > 0:
                df = self.dfs(vt, en, min(nf, c))
                if df > 0:
                    self.edge[nv][i][1] -= df
                    self.edge[vt][r][1] += df
                    return df
            nextv[nv] += 1
        return 0
    def getmf(self, st, en):
        mf = 0
        while True:
            self.bfs(st)
            if self.dist[en] == -1:
                break
            self.nextv = [0]*self.n
            while True:
                fl = self.dfs(st, en, self.inf)
                if fl > 0:
                    mf += fl
                else:
                    break
        return mf

def Fi():
    print('First')
    exit()

N = int(eval(input()))
Edge = [[] for _ in range(N+2)]
for _ in range(N-1):
    a, b = list(map(int, input().split()))
    Edge[a].append(b)
    Edge[b].append(a)

if N % 2:
    Fi()

dist = [0]*(N+1)
visited = set([1])
stack = [1]

while stack:
    vn = stack.pop()
    for vf in Edge[vn]:
        if vf in visited:
            continue
        visited.add(vf)
        dist[vf] = not dist[vn]
        stack.append(vf)

Din = Dinic(N+2)

for i in range(1, N+1):
    if dist[i]:
        Din.addedge(0, i, 1)
        for j in Edge[i]:
            Din.addedge(i, j, 1)
    else:
        Din.addedge(i, N+1, 1)

if Din.getmf(0, N+1) != N//2:
    Fi()
print('Second')


# Optimized solution
from sys import exit
def Fi():
    print('First')
    exit()

N = int(eval(input()))
dim = [-1]*N
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = list(map(int, input().split()))
    dim[a-1] += 1
    dim[b-1] += 1
    Edge[a-1].append(b-1)
    Edge[b-1].append(a-1)
par = [None] + [0]*(N-1)
stack = [0]
visited = set([0])
while stack:
    vn = stack.pop()
    for vf in Edge[vn]:
        if vf in visited:
            continue
        visited.add(vf)
        par[vf] = vn
        stack.append(vf)

L = [i for i in range(1,N) if dim[i] == 0]
used = set(L)
stack = L[:]
mat = [0]*N
dim[0] += 2
while stack:
    vn = stack.pop()
    pv = par[vn]
    if pv is None:
        break
    if mat[vn] == 0:
        mat[vn] += 1
        mat[pv] += 1
    dim[pv] -= 1
    if dim[pv] == 0:
        stack.append(pv)
print(('Second' if all(m == 1 for m in mat) else 'First'))