Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

a = list(map(int, input().split()))

nums = [0] * (10**5+1)
nums[0] = a.count(0) + a.count(1)
nums[(10**5)] = a.count((10**5)-1) + a.count((10**5))
for i in range(1, (10**5)):
  nums[i] = a.count(i-1) + a.count(i) + a.count(i+1)
  
print(max(nums))

Fixed submission:
n = int(input())

a = list(map(int, input().split()))

d = {}

for i in a:
  for j in range(i - 1, i + 2): #aの値の両隣まで
    d[j] = d.get(j, 0) + 1#getは第一引数で指定したキーがなかったら第二引数で指定した値を戻す
    
    
print(max(d.values()))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

a = list(map(int, input().split()))

checked = []
zipped = zip(list(range((10**5+1))), [0]*(10**5+1))
nums = dict(zipped)
for i in a:
  if i not in checked:
    nums[i] = a.count(i)
    checked.append(i)
  
  
totals = [0] * (10**5 + 1)
for i in nums:
  if i == 0:
    totals[0] = nums[0] + nums[1]
  elif i == (10**5):
    totals[0] = nums[10**5-1] + nums[10**5]
  else:
    totals[i] = nums[i-1] + nums[i] + nums[i+1]
  
  
print(max(totals))  

Fixed submission:
n = int(input())

a = list(map(int, input().split()))

d = {}

for i in a:
  for j in range(i - 1, i + 2): #aの値の両隣まで
    d[j] = d.get(j, 0) + 1#getは第一引数で指定したキーがなかったら第二引数で指定した値を戻す
    
    
print(max(d.values()))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

a = list(map(int, input().split()))

checked = []
zipped = zip(list(range((10**5+1))), [0]*(10**5+1))
nums = dict(zipped)
for i in a:
  if i not in checked:
    nums[i] = a.count(i)
    checked.append(i)
  
  
totals = [0] * (10**5 + 1)
for i in nums:
  if i == 0:
    totals[0] = nums[0] + nums[1]
  elif i == (10**5):
    totals[0] = nums[10**5-1] + nums[10**5]
  else:
    totals[i] = nums[i-1] + nums[i] + nums[i+1]
  
  
print(max(totals))  

Fixed submission:
n = int(input())

a = list(map(int, input().split()))

d = {}

for i in a:
  for j in range(i - 1, i + 2): #aの値の両隣まで
    d[j] = d.get(j, 0) + 1#getは第一引数で指定したキーがなかったら第二引数で指定した値を戻す
    
    
print(max(d.values()))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
INF = float("inf")
es = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N-1):
    a,b,c = map(int, input().split())
    a,b = a-1, b-1
    es[a][b] = c
    es[b][a] = c

Q, K = map(int, input().split())
xy = []
for i in range(Q):
    x,y = map(int, input().split())
    xy.append([x-1, y-1])

checked = [False] * N

d = [INF] * N
d[K-1] = 0
def dijkstra(s):
    while True:
        v = -1
        for i in range(N):
            if checked[i] == False and v == -1:
                v = i
            elif checked[i] == False and d[i] < d[v]:
                v = i
        if v == -1:
            break
        
        checked[v] = True
        for i in range(N):
            d[i] = min(d[i], d[v] + es[v][i])
    return

dijkstra(K-1)

for x,y in xy:
    print(d[x] + d[y])


Fixed submission:
import sys
sys.setrecursionlimit 
N = int(input())
# 再帰の深さを増やしておく
sys.setrecursionlimit(10**9+1)

nodes = [[] for _ in range(N+1)]
for i in range(N-1):
      a,b,c, = map(int, input().split())
      # a->bとb->aの両方について保存
      nodes[a].append((b,c))
      nodes[b].append((a,c))

memo = [0] * (N+1)

# searchedというdistを持たせて調べた場所を管理するのも可能か
def dfs(cur, prev, dist):
      # ある地点（K）から現在地点までのコストを記入しておくことで、最終的にKから他のノードまでの距離が記入される
      memo[cur] = dist
      # nodes[a]から移動できる先と距離を取り出す
      for next, cost in nodes[cur]:
            # 移動前に戻ると無限ループするので飛ばす。searchedなりを持たせてもいい
            if next == prev:
                  continue
            # 移動先について探索を行う
            dfs(next, cur, dist+cost)

Q,K = map(int, input().split())
dfs(K, 0, 0)
for _ in range(Q):
      x,y = map(int, input().split())
      print(memo[x]+memo[y])
Buggy python submission (verdict: Time Limit Exceeded):


N,M = map(int, input().split())

es = [[] for _ in range(N+1)]

for i in range(M):
    a,b = map(int, input().split())
    es[a].append(b)


for i in range(2,N):
    if i in es[1] and N in es[i]:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Fixed submission:
n,m = map(int, input().split())

ship = {}

for i in range(m):
  a,b = (map(int, input().split()))
  if a == 1 or b == n:
    if a in ship: #keyにaがあるばあい
      ship[a].append(b)
    else:
      ship[a] = [b]

if 1 in ship:
  for i in ship[1]:
    if i in ship and n in ship[i]:
      print("POSSIBLE")
      exit()
      


  
  
print("IMPOSSIBLE")

Buggy python submission (verdict: Time Limit Exceeded):


from collections import defaultdict

N, M = map(int, input().split())
es = defaultdict(list)
for i in range(M):
    a,b = map(int, input().split())
    es[a].append(b)


for i in range(2,N):

    if i in es[1] and N in es[i]:
        print("POSSIBLE")
        exit()


print("IMPOSSIBLE")

Fixed submission:
n,m = map(int, input().split())

ship = {}

for i in range(m):
  a,b = (map(int, input().split()))
  if a == 1 or b == n:
    if a in ship: #keyにaがあるばあい
      ship[a].append(b)
    else:
      ship[a] = [b]

if 1 in ship:
  for i in ship[1]:
    if i in ship and n in ship[i]:
      print("POSSIBLE")
      exit()
      


  
  
print("IMPOSSIBLE")

Buggy python submission (verdict: Runtime Error):
n,m = map(int, input().split())

ship = {}

for i in range(m):
  a,b = (map(int, input().split()))
  if a == 1 or b == n:
    if a in ship: #keyにaがあるばあい
      ship[a].append(b)
    else:
      ship[a] = [b]

        
for i in ship.keys():
  if n in ship[i]:
    print("POSSIBLE")
    exit()
  else:
    for j in ship[i]:
      if n in ship[j]:
        print("POSSIBLE")
        exit()
      

  
  
print("IMPOSSIBLE")

Fixed submission:
n,m = map(int, input().split())

ship = {}

for i in range(m):
  a,b = (map(int, input().split()))
  if a == 1 or b == n:
    if a in ship: #keyにaがあるばあい
      ship[a].append(b)
    else:
      ship[a] = [b]

if 1 in ship:
  for i in ship[1]:
    if i in ship and n in ship[i]:
      print("POSSIBLE")
      exit()
      


  
  
print("IMPOSSIBLE")
Buggy python submission (verdict: Runtime Error):


K = int(input())
N = 50
# 最後の状態からさかのぼる
A = [49] * 50
# K を均等に割り振る（どれか一つを集中して選択しない）
for i in range(N):
    A[i] += K // 50
# 割り振った残りを、さらになるべく均等に割り振る
for i in range(K // N):
    A[i] += 51
    for j in range(N):
        A[j] -= 1

print(N)
print(*A)

Fixed submission:


K = int(input())
N = 50
# 最後の状態からさかのぼる
A = [49] * 50
# K を均等に割り振る（どれか一つを集中して選択しない）
for i in range(N):
    A[i] += K // 50
# 割り振った残りを、さらになるべく均等に割り振る
for i in range(K % N):
    A[i] += 51
    for j in range(N):
        A[j] -= 1

print(N)
print(*A)
Buggy python submission (verdict: Runtime Error):

N,K = map(int, input().split())

A = list(map(int, input().split()))

A.sort()

if A[-1] < K:
    print("IMPOSSIBLE")
    exit()

if K in A or 1 in A:
    print("POSSIBLE")
    exit()

def gcd(a,b):
    x = max([a,b])
    y = min([a,b])
    while y:
        x, y = y, x % y
    return x

g = A[0]
for i in range(1,N):
    g = gcd(A[i], g)
    

print("POSSIBLE" ig K % g == 9 else "IMPOSSIBLE")

Fixed submission:
N,K = map(int, input().split())

A = list(map(int, input().split()))

A.sort()

if A[-1] < K:
    print("IMPOSSIBLE")
    exit()

if K in A or 1 in A:
    print("POSSIBLE")
    exit()

def gcd(a,b):
    x = max([a,b])
    y = min([a,b])
    while y:
        x, y = y, x % y
    return x

g = A[0]
for n in A[1:]:
    g = gcd(n, g)
    

print("POSSIBLE" if K % g == 0 else "IMPOSSIBLE")
Buggy python submission (verdict: Runtime Error):
#普通にやるとTLE
n = int(input())

a = list(map(int, input().split()))

total = sum(a)
ans = float("inf")
for i in range(n-1):
  x += a[i]
  y = total - x
  if(abs(x-y) < ans):
    ans = abs(x-y)
    
print(ans)

Fixed submission:
n = int(input())

a = list(map(int, input().split()))

total = sum(a)
x = 0
ans = float("inf")
for i in range(n-1):
  x += a[i]
  y = total - x
  if(abs(x-y) < ans):
    ans = abs(x-y)
    
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

a = list(map(int, input().split()))

total = sum(a)
ans = float("inf")
for i in range(n-1):
  x = sum(a[:i+1])
  y = total - x
  if(abs(x-y) < ans):
    ans = abs(x-y)
    
print(ans)

Fixed submission:
n = int(input())

a = list(map(int, input().split()))

total = sum(a)
x = 0
ans = float("inf")
for i in range(n-1):
  x += a[i]
  y = total - x
  if(abs(x-y) < ans):
    ans = abs(x-y)
    
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())

es = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    es[a].append(b)
    es[b].append(a)

"""
相手の取れるマス目を減らすようにとるとよい
相手よりそのマスに近ければそのマスを取得できる
フェネックくん、すぬけ君について初期地点からそれぞれへの距離が必要
"""
def solve(now, depth, depth_list, es, visited):
    visited[now] = True
    depth_list[now] = depth
    for next in es[now]:
        if visited[next] == False:            
            solve(next, depth+1, depth_list, es, visited)

depth_list_F = [0] * N
visited_F = [False] * N
solve(0, 0, depth_list_F, es, visited_F)

depth_list_S = [0] * N
visited_S = [False] * N
solve(N-1, 0, depth_list_S, es, visited_S)

cnt_F = cnt_S = 0
for f,s in zip(depth_list_F, depth_list_S):
    if f <= s:
        cnt_F += 1 # フェネック君から始めるので同じ距離ならフェネック君がとる
    else:
        cnt_S += 1

if cnt_F > cnt_S:
    print("Fennec")
else:
    print("Snuke")

Fixed submission:
N = int(input())
import sys
sys.setrecursionlimit(N+10)

es = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    es[a].append(b)
    es[b].append(a)

"""
相手の取れるマス目を減らすようにとるとよい
相手よりそのマスに近ければそのマスを取得できる
フェネックくん、すぬけ君について初期地点からそれぞれへの距離が必要
"""
def solve(now, depth, depth_list, es, visited):
    visited[now] = True
    depth_list[now] = depth
    for next in es[now]:
        if visited[next] == False:            
            solve(next, depth+1, depth_list, es, visited)

depth_list_F = [0] * N
visited_F = [False] * N
solve(0, 0, depth_list_F, es, visited_F)

depth_list_S = [0] * N
visited_S = [False] * N
solve(N-1, 0, depth_list_S, es, visited_S)

cnt_F = cnt_S = 0
for f,s in zip(depth_list_F, depth_list_S):
    if f <= s:
        cnt_F += 1 # フェネック君から始めるので同じ距離ならフェネック君がとる
    else:
        cnt_S += 1

if cnt_F > cnt_S:
    print("Fennec")
else:
    print("Snuke")
Buggy python submission (verdict: Runtime Error):
N = int(input())

ab = [[] for _ in range(N)]

for i in range(N-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    ab[a].append(b)
    ab[b].append(a)

dF = [0] * N
dS = [0] * N
def dfs(now, d, dlist, visited):
    
    if visited[now] == False:
        dlist[now] = d
        visited[now] = True

        for next in ab[now]:
            dfs(next, d+1, dlist, visited)


vF = [False] * N
dfs(0,0,dF, vF)
vS = [False] * N
dfs(N-1, 0, dS, vS)

cnt_F = 0
cnt_S = 0
for i in range(N):
    if dF[i] <= dS[i]:
        cnt_F += 1
    else:
        cnt_S += 1

#print(dF, dS)
if cnt_F > cnt_S:
    print("Fennec")
else:
    print("Snuke")

Fixed submission:
N = int(input())
import sys

sys.setrecursionlimit(N+10)
ab = [[] for _ in range(N)]

for i in range(N-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    ab[a].append(b)
    ab[b].append(a)

dF = [0] * N
dS = [0] * N
def dfs(now, d, dlist, visited):
    
    if visited[now] == False:
        dlist[now] = d
        visited[now] = True

        for next in ab[now]:
            dfs(next, d+1, dlist, visited)


vF = [False] * N
dfs(0,0,dF, vF)
vS = [False] * N
dfs(N-1, 0, dS, vS)

cnt_F = 0
cnt_S = 0
for i in range(N):
    if dF[i] <= dS[i]:
        cnt_F += 1
    else:
        cnt_S += 1

#print(dF, dS)
if cnt_F > cnt_S:
    print("Fennec")
else:
    print("Snuke")
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

a = list(map(str, input().split()))
b = []
for i in range(n):
  if i % 2 == 0:
    #後ろに追加する場合
    b.append(a[i])
  else:
    b.insert(0,a[i])
    
if n % 2 != 0:
  b.reverse()
  
print(" ".join(b))

Fixed submission:
from collections import deque

n = int(input())

a = list(map(str, input().split()))
b = deque()
for i in range(n):
  if i % 2 == 0:
    #後ろに追加する場合
    b.append(a[i])
  else:
    b.appendleft(a[i])
    
    
    
if n % 2 != 0:
  b.reverse()
  
print(" ".join(b))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

a = list(map(str, input().split()))
b = []
for num in a:
  b.append(num)
  b.reverse()
  
print(" ".join(b))
  


Fixed submission:
from collections import deque

n = int(input())

a = list(map(str, input().split()))
b = deque()
for i in range(n):
  if i % 2 == 0:
    #後ろに追加する場合
    b.append(a[i])
  else:
    b.appendleft(a[i])
    
    
    
if n % 2 != 0:
  b.reverse()
  
print(" ".join(b))
Buggy python submission (verdict: Runtime Error):
n = int(input())
arr = []
passed = []
for i in range(n):
  a = int(input())
  arr.append(a)
  
next_position = 1
ans = 0

while(1):
  next_position = arr[next_position-1]
  #print(position)
  if ans == n
    print(-1)
    break
  #passed.append(next_position)
  ans += 1
  if next_position == 2:
    print(ans)
    break
  

Fixed submission:
n = int(input())
arr = []
passed = []
for i in range(n):
  a = int(input())
  arr.append(a)
  
next_position = 1
ans = 0

while(1):
  next_position = arr[next_position-1]
  #print(position)
  if ans == n:
    print(-1)
    break
  #passed.append(next_position)
  ans += 1
  if next_position == 2:
    print(ans)
    break

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
arr = []
passed = []
for i in range(n):
  a = int(input())
  arr.append(a)
  
next_position = 1
ans = 0

while(1):
  next_position = arr[next_position-1]
  #print(position)
  if next_position in passed:
    print(-1)
    break
  passed.append(next_position)
  ans += 1
  if next_position == 2:
    print(ans)
    break
  

Fixed submission:
n = int(input())
arr = []
passed = []
for i in range(n):
  a = int(input())
  arr.append(a)
  
next_position = 1
ans = 0

while(1):
  next_position = arr[next_position-1]
  #print(position)
  if ans == n:
    print(-1)
    break
  #passed.append(next_position)
  ans += 1
  if next_position == 2:
    print(ans)
    break
Buggy python submission (verdict: Time Limit Exceeded):
import heapq



N = int(input())
xy = [None] * N
yx = [None] * N

for i in range(N):
    x,y = map(int, input().split())
    xy[i] = (x, y, i)
    yx[i] = (y, x, i)


xy.sort()
yx.sort()


es = [[] for _ in range(N)]
for i in range(N-1):
    heapq.heappush(es[xy[i][2]], (abs(xy[i][0] - xy[i+1][0]), xy[i+1][2]))
    heapq.heappush(es[xy[i+1][2]], (abs(xy[i][0] - xy[i+1][0]), xy[i][2]))

    heapq.heappush(es[yx[i][2]], (abs(yx[i][0] - yx[i+1][0]), yx[i+1][2]))
    heapq.heappush(es[yx[i+1][2]], (abs(yx[i][0] - yx[i+1][0]), yx[i][2]))


used = [False] * N
used[0] = True
ans = 0

q = []
for c,nxt in es[0]:
    heapq.heappush(q, (c, nxt))

while q:
    c, curr = heapq.heappop(q)
    
    if used[curr]:
        continue

    used[curr] = True
    for nc, nxt in es[curr]:
        heapq.heappush(q, (nc, nxt))
    ans += c

print(ans)

Fixed submission:
N = int(input())
towns = [tuple(map(int, input().split())) for _ in range(N)]

xs = []
ys = []

for i, (x,y) in enumerate(towns):
    xs.append((x, i))
    ys.append((y, i))

xs.sort()
ys.sort()

es = []
for (x1, i1), (x2, i2) in zip(xs, xs[1:]):
    es.append((x2-x1, i1, i2)) #i1からi2までのコストがx2-x1、絶対値とってないけど

for (y1, i1), (y2, i2) in zip(ys, ys[1:]):
    es.append((y2-y1, i1, i2)) #i1からi2までのコストがy2-y1、
es.sort()

class UnionFind:
    def __init__(self, N):
        #初めの親ノードはすべて異なる
        self.parent = [i for i in range(N)]
        #木の高さ
        self.rank = [0] * N
        self.count = 0

    #どのUnionに所属するか判定
    def root(self, a):
        #親が根の場合
        if self.parent[a] == a:
            return a
        else:
            #親の親を調べなおす＆見つかった根に接続しなおす
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]

    #同じUnionか判定
    def is_same(self, a, b):
        return self.root(a) == self.root(b)

    #Unionを作る
    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return
        #高いほうの下に小さいほうを繋ぐ
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count +=1


ans = 0
uf = UnionFind(N)
for d,a,b in es:
    #すでに繋がれてるならスキップ
    if uf.is_same(a,b):
        continue
    uf.unite(a,b) #esはソート済みのため短い順から重複をせずにN個の町が繋がれることが保証される
    ans += d
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):

import math
n,a,b = map(int, input().split())

m = [0] * n
for i in range(n):
  m[i] = int(input())
  

m.sort()


def enough(m,a,b,T):
  cnt = 0
  for hp in m:
    if hp > b*T:
      cnt += int(math.ceil((hp - b*T)/(a-b)))
      
  return True if  cnt <= T else False

r = 10**100
#r = 30
l = 0
mid = 0

while r - l > 1:
  mid = (r+l)//2
  if enough(m,a,b,mid) == True:
    r = mid
    #print("r:",r)
  else:
    l = mid
    #print("l:",l, " r:",r)

print(r)

Fixed submission:

import math
n,a,b = map(int, input().split())

m = [0] * n
for i in range(n):
  m[i] = int(input())
  

m.sort()


def enough(m,a,b,T):
  cnt = 0
  for hp in m:
    if hp > b*T:
      cnt += int(math.ceil((hp - b*T)/(a-b)))
      
  return True if  cnt <= T else False

r = 10**10
#r = 30
l = 0
mid = 0

while r - l > 1:
  mid = (r+l)//2
  if enough(m,a,b,mid) == True:
    r = mid
    #print("r:",r)
  else:
    l = mid
    #print("l:",l, " r:",r)

print(r)
Buggy python submission (verdict: Runtime Error):
o = list(input())
e = list(input())

ans = []
for i in range(len(o)):
  ans.append(o[i])
  if e[i]:
    ans.append(e[i])
    
print("".join(ans))

Fixed submission:
o = list(input())
e = list(input())

ans = []
for i in range(len(o)):
  ans.append(o[i])
  if i < len(o)-1:
    ans.append(e[i])
  else:
    if len(e) == len(o):
      ans.append(e[i])
    
print("".join(ans))
Buggy python submission (verdict: Time Limit Exceeded):
s, c = map(int, input().split())

ans = 0

if 2*s >= c:
  ans = c // 2
else:
  while 2*s < c and 2*(s+1) <= c-2:
    c -= 2
    s += 1
  ans = s
  
print(ans)

Fixed submission:
s, c = map(int, input().split())

ans = 0
#手持ちのSで作れる分だけSccを作る
if c <= 2*s:
  ans += c // 2
  c = c%2
  s = 0
else:
  ans += s
  c = c - 2*s
  s = 0
  


#print(s)
#print(c)
#print(ans)
#まだcが余ってたらSccを作る
if c >= 4:
  ans += c // 4
  
print(ans)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())

if M == 0:
    print(0)
    exit()

es = [[] for i in range(M)]
for i in range(M):
    a, b = map(int, input().split())
    a,b = a-1, b-1
    es[a].append(b)
    es[b].append(a)

def dfs(v, visited, es, cnt):

    #print("--------------")
    #print((v, visited, cnt))

    if cnt == N-1:
        return 1
    ret = 0
    for i in es[v]:
        if visited[i] == True:
            continue

        visited[i] = True
        ret += dfs(i, visited, es, cnt+1)
        visited[i] = False

    return ret

visited = [False] * N
visited[0] = True

ans = dfs(0,visited,es,0)
print(ans)

Fixed submission:
import copy
n,m = map(int, input().split())


paths = [[] for _ in range(n)]
for i in range(m):
  a,b = map(int, input().split())
  paths[a-1].append(b-1)
  paths[b-1].append(a-1)
  
ans = 0

checked = [False for _ in range(n)]


def solve(i, c):
  c[i] = True

  global ans
  if c.count(False) == 0:
    ans += 1
    return
  else:
    for j in paths[i]:
      if c[j] == False: 
        solve(j, copy.deepcopy(c))
        
      

        
solve(0, copy.deepcopy(checked))
print(ans)
    
#print(paths[0])

Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())

es = [[] for i in range(M)]
for i in range(M):
    a, b = map(int, input().split())
    a,b = a-1, b-1
    es[a].append(b)
    es[b].append(a)

def dfs(v, visited, es, cnt):

    #print("--------------")
    #print((v, visited, cnt))

    if cnt == N-1:
        return 1
    ret = 0
    for i in es[v]:
        if visited[i] == True:
            continue

        visited[i] = True
        ret += dfs(i, visited, es, cnt+1)
        visited[i] = False

    return ret

visited = [False] * N
visited[0] = True

ans = dfs(0,visited,es,0)
print(ans)

Fixed submission:
import copy
n,m = map(int, input().split())


paths = [[] for _ in range(n)]
for i in range(m):
  a,b = map(int, input().split())
  paths[a-1].append(b-1)
  paths[b-1].append(a-1)
  
ans = 0

checked = [False for _ in range(n)]


def solve(i, c):
  c[i] = True

  global ans
  if c.count(False) == 0:
    ans += 1
    return
  else:
    for j in paths[i]:
      if c[j] == False: 
        solve(j, copy.deepcopy(c))
        
      

        
solve(0, copy.deepcopy(checked))
print(ans)
    
#print(paths[0])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

a = list(map(int, input().split()))
set_a = set(a)
nums = {}
cnt = 0
for i in set_a:
    nums[i] = a.count(i)
    if a.count(i) % 2 == 0:
        cnt += 1
    elif a.count(i) != 1:
        cnt += 2

print(len(set_a) - cnt%2)

Fixed submission:
n = int(input())

a = list(map(int, input().split()))
set_a = set(a)
nums = {}
cnt = 0

for i in range(n):
    nums[a[i]] = nums.get(a[i], 0) + 1


for i in set_a:
    if nums[i] % 2 == 0:
        cnt += 1
    elif nums[i] != 1:
        cnt += 2

print(len(set_a) - cnt%2)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

a = list(map(int, input().split()))
set_a = set(a)
nums = {}
cnt = 0
for i in set_a:
    nums[i] = a.count(i)
    if a.count(i) % 2 == 0:
        cnt += 1
    elif a.count(i) != 1:
        cnt += 2

print(len(set_a) - cnt%2)

Fixed submission:
n = int(input())

a = list(map(int, input().split()))
set_a = set(a)
nums = {}
cnt = 0

for i in range(n):
    nums[a[i]] = nums.get(a[i], 0) + 1


for i in set_a:
    if nums[i] % 2 == 0:
        cnt += 1
    elif nums[i] != 1:
        cnt += 2

print(len(set_a) - cnt%2)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

a = list(map(int, input().split()))
set_a = set(a)
nums = {}
cnt = 0
for i in set_a:
    nums[i] = a.count(i)
    if a.count(i) % 2 == 0:
        cnt += 1
    else:
        if a.count(i) == 1:
            continue
        else:
            cnt += 2

print(len(set_a) - cnt%2)

Fixed submission:
n = int(input())

a = list(map(int, input().split()))
set_a = set(a)
nums = {}
cnt = 0

for i in range(n):
    nums[a[i]] = nums.get(a[i], 0) + 1


for i in set_a:
    if nums[i] % 2 == 0:
        cnt += 1
    elif nums[i] != 1:
        cnt += 2

print(len(set_a) - cnt%2)