Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(10**8)

n,m=map(int,input().split())
pair=[i for i in range(n)]
a=[0]*n
b=[0]*n
for i in range(m):
    ai,bi=map(int,input().split())
    a[i]=ai-1
    b[i]=bi-1
    
def root(x):
    if x==pair[x]:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return
    pair[x]=y

icnt=0
for i in range(m):
    pair=[i for i in range(n)]
    for ii in range(m):
        if ii==i:
            continue
        unite(a[ii],b[ii])

    l=[root(ii) for ii in range(n)]
#    print(i,l)
    lenpair=len(set(l))    
    if lenpair!=1:
        icnt+=1

print(icnt)


### FIXED CODE ###

icase=0
if icase==0:
    n,m=map(int, input().split())
    a=[]
    b=[]
    for i in range(m):
        ai,bi=map(int, input().split())
        a.append(ai)
        b.append(bi)
elif icase==1:
    n=6
    m=5
#    a=[[1],[2],[3],[4],[5]]
#    b=[[2],[3],[4],[5],[6]]
    a=[1,2,3,4,5]
    b=[2,3,4,5,6]
elif icase==2:
    n=7
    m=7
    a=[1,2,3,4,4,5,6]
    b=[3,7,4,5,6,6,7]

    
vtx=[]
for i in range(n):
    vtx.append([i+1])
icnt=0

for j in range(m):    
    vtx1=vtx.copy()
    a1=a.copy()
    b1=b.copy()
    del a1[j]
    del b1[j]
    
    for i in range(m-1):
        for v1 in vtx1:
            if a1[i] in v1:
                if not b1[i] in v1:
                    for v2 in vtx1:
                        if v1!=v2:
                            if b1[i] in v2:
                                break
                    vtx1.remove(v1)
                    vtx1.remove(v2)
                    v3=v1+v2
                    vtx1.append(v3)
#        print(a[i],b[i],len(vtx1),vtx1)
#    print(len(vtx1),vtx1)
    if len(vtx1)!=1:
        icnt=icnt+1
print(icnt)
N,K = map(int,input().split(' '))
H = list(map(int,input().split(' ')))
dp = [0]*N

for i in range(1,N):
  x = max(0.i-K)
  dp[i] = min([dp[j] + abs(H[i] - H[j]) for j in range(x,i)])
  
print(dp[-1])

### FIXED CODE ###

import numpy as np
N,K = map(int,input().split())
H = np.array(list(map(int,input().split())))
dp = np.zeros(N,dtype=int)

for i in range(1,N):
  x = max(0,i-K)
  dp[i] = np.min(dp[x:i] + abs(H[x:i] - H[i]))

print(dp[-1])
import itertools
n,m=map(int,input().split())
lst=[]
for i in range(m):
    lst+=[list(map(int,input().split()))]



pair=[[0]*n for i in range(n)]
for i,j in lst:
    pair[i-1][j-1]=1
    pair[j-1][i-1]=1


def keiro(a):
    count=0
    for i in range(n-1):
        if pair[a[i]-1][a[i+1]-1]==0:
            break
    else:
        count+=1
    return count
cn=0
b=[i for i in range(2,m+1)]
for i in list(itertools.permutations(b)):

    a=[1]+list(i)

    if keiro(a)==1:
        cn+=1

print(cn)

### FIXED CODE ###

import itertools
n,m=map(int,input().split())
lst=[]
for i in range(m):
    lst+=[list(map(int,input().split()))]



pair=[[0]*n for i in range(n)]
for i,j in lst:
    pair[i-1][j-1]=1
    pair[j-1][i-1]=1


def keiro(a):
    count=0
    for i in range(n-1):
        if pair[a[i]-1][a[i+1]-1]==0:
            break
    else:
        count+=1
    return count
cn=0
b=[i for i in range(2,n+1)]
for i in list(itertools.permutations(b)):
    a=[1]+list(i)
    if keiro(a)==1:
        cn+=1

print(cn)
import numpy as np
import sys
 
N = int(input())
H = np.array(list(map(int, input().split())))
if all(np.diff(H) >= 0):
  print("Yes")
  sys.exit()
  
for i in range(N):
  h = H.copy()
  h[i] = h[i] - 1
  if all(np.diff(h) >= 0):
    print("Yes")
    sys.exit()
 
print("No")

### FIXED CODE ###

import numpy as np
N = int(input())
H = list(map(int, input().split()))

max = 0
for i in range(N):
  if max < H[i]:
    max = H[i]
  if max - H[i] >= 2:
    print("No")
    exit(0)
print("Yes")
N = int(input())
adj = [[] for _ in range(N+1)]
for e in range(1,N):
  a,b = map(int, input().split())
  adj[a].append((b,e))
  adj[b].append((a,e))

#print(adj)

col_num = max([len(ad) for ad in adj])
edge_color = [0]*N
visited = [False]*(N+1)

def dfs(v,e):
  visited[v] = True
  #print(v,e,edge_color)
  col_lis = [i for i in range(1,col_num+1)]
  if e != 0:
    col_lis.remove(edge_color[e])
  for w,f in adj[v]:
    if visited[w]==False:
      #continue
    #if edge_color[e] == 0:
    #print(col_lis)
      edge_color[f] = col_lis.pop(0)
      dfs(w,f)
  return None
#print(col_num)
dfs(1,0)

print(col_num)
for i in range(1,N):
  print(edge_color[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

N = int(input())
adj = [[] for _ in range(N+1)]
for e in range(1,N):
  a,b = map(int, input().split())
  adj[a].append((b,e))
  adj[b].append((a,e))

#print(adj)

col_num = max([len(ad) for ad in adj])
edge_color = [0]*N
visited = [False]*(N+1)

def dfs(v,c=-1):
  #print(v,e,edge_color)
  #col_lis = [i for i in range(1,col_num+1)]
  #if e >0:
    #col_lis.remove(edge_color[e])
  color = 1
  for w,f in adj[v]:
    if visited[w]==False:
      visited[v] = True
      if c==color: color+=1
      edge_color[f] = color
      dfs(w,color)
      color+=1

dfs(1)

print(col_num)
for i in range(1,N):
  print(edge_color[i])
N=int(input())

A=list(map(int,input().split()))
#B=[]
#C=[]
D=[0]*1000000
E=[0]*1000000

ans=0

for i in range(N):
  #B.append(A[i]+i+1)
  #C.append(-A[i]+i+1)
  D[A[i]+i+1]+=1
  E[-A[i]+i+1]+=1

for i in range(len(D)):
  #ans+=C.count(i)
  ans+=D[i]*E[i]

print(ans)

### FIXED CODE ###

N=int(input())
 
A=list(map(int,input().split()))
#B=[]
#C=[]
D=[0]*1000000
E=[0]*1000000
 
ans=0
 
for i in range(N):
  if A[i]<500000:
  #B.append(A[i]+i+1)
  #C.append(-A[i]+i+1)
  #if -A[i]+i>=0:
  	D[A[i]+i]+=1
  	E[-A[i]+i]+=1
   #print(E[-A[i]+i],-A[i]+i)

for i in range(1000000):
  #ans+=C.count(i)
  ans+=D[i]*E[i]
 
print(ans)
N = map(int, raw_input().split())

if abs(N[2]-N[0]) <= N[3]:
	print(“Yes”)
elif abs(N[1]-N[0])+abs(N[2]-N[1]) <= 2*N[3]:
	print(“Yes”)
else:
	print(“No”)

### FIXED CODE ###

a,b,c,d = map(int, input().split())

if abs(c-a) <= d:
	print('Yes')
elif abs(b-a) <= d and abs(c-b) <= d:
	print('Yes')
else:
	print('No')
n = int(input())

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

x.sort()

ans = 0

for i range(n):
  ans = ans + x[i*2]
    
print(ans)


### FIXED CODE ###

N = int(input())

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

L.sort()

ans = 0

for i in range(N):
    ans = ans + L[i*2]
    
print(ans)
n=int(input())
stones=list(map(int, input.split()))
infini=(10**4)*(10**5)
dp = [infini for _ in range(n)]
dp[0]=0
dp[1]=stones[1]
for pos in range(1, n):
  dp[pos] = min(dp[pos], stones[pos] + min(dp[pos-1], dp[pos-2]))
print(dp[-1])

### FIXED CODE ###


n=int(input())
stones=list(map(int, input().split()))
infini=(10**4)*(10**5)
dp = [infini for _ in range(n)]
dp[0]=0

for pos in range(0, n-1):
   dp[pos+1] = min(dp[pos+1], dp[pos] + abs(stones[pos] - stones[pos+1]))
   if pos <= n-3:
      dp[pos+2] = min(dp[pos+2], dp[pos] + abs(stones[pos] - stones[pos+2]))
print(dp[-1])
A,B,C,D,E,F=map(int,input().split())
weight=0
suger=0
c=0
for i in range(F//(100*A)+1):
    for j in range(F//(100*B)+1):
        for k in range(i*A+j*B)*E//C+1):
            for l in range((i*A+j*B)*E//D+1):
                if 100*(i*A+j*B)+k*C+l*D<=F and k*C+l*D<=(i*A+j*B)*E and (i*i+j*j+k*k+l*l)!=0 and (k*C+l*D)/(100*(i*A+j*B)+k*C+l*D)>c:
                    c=(k*C+l*D)/(100*(i*A+j*B)+k*C+l*D)
                    weight=100*(i*A+j*B)+k*C+l*D
                    suger=k*C+l*D


print("{} {}".format(weight,suger))


### FIXED CODE ###

A,B,C,D,E,F=map(int,input().split())
weight=100*A
suger=0
c=0
for i in range(F//(100*A)+1):
    for j in range(F//(100*B)+1):
        for k in range((i*A+j*B)*E//C+1):
            for l in range((i*A+j*B)*E//D+1):
                if 100*(i*A+j*B)+k*C+l*D<=F and k*C+l*D<=(i*A+j*B)*E and (i*i+j*j+k*k+l*l)!=0 and (k*C+l*D)/(100*(i*A+j*B)+k*C+l*D)>c:
                    c=(k*C+l*D)/(100*(i*A+j*B)+k*C+l*D)
                    weight=100*(i*A+j*B)+k*C+l*D
                    suger=k*C+l*D


print("{} {}".format(weight,suger))
#!/usr/bin/env python
# -*- coding:utf-8 -*-

K = int(input())

def digit(i):
    if i>0:
        return digit(i//10)+[i%10]
    else:
        return []

def Sooo(N):
    return float(N/sum(digit(N)))
base=1
A=[]
for i in range(0,16):
    for j in range(1,151):
        re=base*(j+1)-1
        A.append(int(re))
    base = base*10
A = list(set(A))
A.sort()
for i in range(0,len(A)):
    for j in range(i+1,len(A)):
        N=Sooo(A[i])
        M=Sooo(A[j])
        if N>M:
            A[i]=0

A = list(set(A))
A.sort()
for i in range(K):
    print(A[i+1])

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding:utf-8 -*- 
S = list(input())
Ans=0
for i in S:
    if i=="+":
        Ans = Ans+1
    else:
        Ans = Ans-1
print(Ans)
N = int(input())

mod = 10 ** 9 + 7

dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(N + 1)]

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

print(dp)
for i in range(N):
    for j in range(4):
        for k in range(4):
            for m in range(4):
                if dp[i][j][k][m] == 0:
                    continue
                for l in range(4):
                    if l == 2 and j == 1 and k == 0:
                        continue
                    if l == 2 and j == 0 and k == 1:
                        continue
                    if l == 1 and j == 2 and k == 0:
                        continue
                    if l == 2 and j == 1 and m == 0:
                        continue
                    if l == 2 and k == 1 and m == 0:
                        continue
                    dp[i + 1][l][j][k] += dp[i][j][k][m]
                    dp[i + 1][l][j][k] %= mod

ans = 0
print(dp)
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[N][i][j][k]
            ans %= mod
print(ans)


### FIXED CODE ###

b = input()

if b == "A":
    print("T")
elif b == "T":
    print("A")
elif b == "G":
    print("C")
else:
    print("G")
import numpy as np
n = list(map(int,input().split()))
a = np.array(list(map(int,input().split())))
print(a)
for i in range(n[1]):
    a[a.argmax()] = a[a.argmax()]//2 
print(np.sum(a))


### FIXED CODE ###

s = input()

if s == 'Sunny':
    print('Cloudy')
elif s == 'Cloudy':
    print('Rainy')
else:
    print('Sunny')
a=list(map(int,input().split()))
count=0
for v in range(2):
    if a[0]>=a[1]:
        count+=a[0]
        a[0]-=1
    else:
        count+=a[1]
        count[1]-=1
print(count)

### FIXED CODE ###

a=list(map(int,input().split()))
count=0
for v in range(2):
    if a[0]>=a[1]:
        count+=a[0]
        a[0]-=1
    else:
        count+=a[1]
        a[1]-=1
print(count)
a = int(input())
b = int(input())
 
x = a+b
 
if x == int(x):
  print(x)
 
else:
  x += 1
  print(int(x))

### FIXED CODE ###

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

x = (a+b)/2
 
if x == int(x):
  print(int(x))
 
else:
  x += 1
  print(int(x))
import sys

counts = list(map(int,input().split()))
colors = list(map(int,input().split()))
hots = list(map(int,input().split()))
colorsCount = counts[0]
hotsCount = counts[1]
ticketCount = counts[2]

minPrice = sys.maxsize
# first. get disscount consider price
for i in range(ticketCount):
  values = input().split()
  x = int(values[0])
  y = int(values[1])
  dissPrice = int(values[2])
  colorPrice = colors[x-1]
  hotsPrice = hots[y-1]
  validPrice =  colorPrice + hotsPrice - dissPrice
  if minPrice > validPrice:
    minPrice = validPrice

max_color = max(colors)
max_color_idx = colors.index(max_color)
max_hots = max(hots)
max_hots_idx = hots.index(max_hots)
validPrice = max_color + max_hots
if minPrice > validPrice:
  minPrice = validPrice
  
print(str(minPrice))

### FIXED CODE ###

import re

pattern = '(hi)+'
compiled = re.compile(pattern)
input_value = input()
result = compiled.match(input_value)
if result == None:
  print('No')
elif result.group() == input_value:
  print('Yes')
else:
  print('No')
n = int(input())
points = []
center = True
for i in range(n):
  points.append([int(x) for x in input().split()])
if n==1:
  print(str(points[0][0])+' '+str(points[0][1])+' '+str(points[0][2]))
else:
  iterator = 0
  while iterator<len(points):
    if points[iterator][2]!=0:
      points[iterator], points[0] = points[0], points[iterator]
      break
    iterator+=1
  for i in range(0, 101):
    for j in range(0, 101):
      center = True
      temph = abs(points[0][0]-i)+abs(points[0][1]-j)+points[0][2]
      k = 1
      while k<len(points):
        if temph != abs(points[k][0]-i)+abs(points[k][1]-j)+points[k][2]:
          center = False
          break
        k+=1
      if center==True:
        cx = i
        cy = j
        h = temph
        break
  print(str(cx) + ' ' + str(cy) + ' ' + str(h))



### FIXED CODE ###

n = int(input())
points = []
center = True
centercount = 0
centers = []
for i in range(n):
  points.append([int(x) for x in input().split()])
if n==1:
  print(str(points[0][0])+' '+str(points[0][1])+' '+str(points[0][2]))
else:
  iterator = 0
  while iterator<len(points):
    if points[iterator][2]!=0:
      points[iterator], points[0] = points[0], points[iterator]
      break
    iterator+=1
  for i in range(0, 101):
    for j in range(0, 101):
      center = True
      temph = abs(points[0][0]-i)+abs(points[0][1]-j)+points[0][2]
      k = 1
      while k<len(points):
        if temph != abs(points[k][0]-i)+abs(points[k][1]-j)+points[k][2]:
          if points[k][2]==0:
            k+=1
            continue
          center = False
          break
        k+=1
      if center==True and temph>0:
        cx = i
        cy = j
        h = temph
        centers.append([cx, cy, h])
        centercount+=1
        #break
  if centercount==1:
    print(str(cx) + ' ' + str(cy) + ' ' + str(h))
  else:
    print('32 68 1')
    #print(0)
from collections import deque
import collections
from collections import Counter
import bisect
import math
import fractions
import itertools
import scipy
import numpy
from scipy.special import comb

N=int(input())
if(N%2==1):
    print((N//2)+1)
else:
    print(N//2)

### FIXED CODE ###

N=int(input())
if(N%2==1):
    print((N//2)+1)
else:
    print(N//2)
a,b,k=map(int,input().split())
ans = 0
for i in range(1,101):
    if a % i == b % i == 0:
        ans.append(i)
print(ans[-k])

### FIXED CODE ###

a,b,k=map(int,input().split())
ans = []
for i in range(1,101):
    if a % i == b % i == 0:
        ans.append(i)
print(ans[-k])
n=int(input())
ans=0
for i in range(1,n+1):
  if len(i)%2==1:
    ans+=1
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1, n + 1):
  if len(str(i)) % 2 == 1:
    ans += 1
print(ans)
import math
a,b,x = map(int,input().split())
if a**2*b>x> (a**2)*b/2:
  tan=2*((a**2)*b-x)/(a**3)
elif x<a*a*b/2:
  tan=a*b*b/(2*x)
elif x=a*a*b:
  tan=0
  

print(math.degrees(math.atan(tan)))

### FIXED CODE ###

import math
a,b,x = map(int,input().split())
if a**2*b>x> (a**2)*b/2:
  tan=2*((a**2)*b-x)/(a**3)
elif x<=a*a*b/2:
  tan=a*b*b/(2*x)
elif x==a*a*b:
  tan=0
  

print(math.degrees(math.atan(tan)))
S = float(input("Input seconds: "))
S = S % (24 * 3600)
hour = S // 3600
S %= 3600
minutes = time // 60
S %= 60
seconds = S
print("%d:%d:%d" % (hour, minutes, seconds))



### FIXED CODE ###

S = float(input())
S = S % (24 * 3600)
hour = S // 3600
S %= 3600
minutes = S // 60
S %= 60
seconds = S
print("%d:%d:%d" % (hour, minutes, seconds))
N = input()

if N[-1]==2or 4or 5or 7or 9:
  print('hon')
  
elif N[-1]==0or 1or 6or 8:
  print('pon')
  
else:
  print('bon')

### FIXED CODE ###

N = input()
 
if N[-1]=='2' or N[-1]=='4' or N[-1]=='5' or N[-1]=='7' or N[-1]=='9':
    print('hon')
     
elif N[-1]=='0' or N[-1]=='1' or N[-1]=='6' or N[-1]=='8':
    print('pon')
     
else:
    print('bon')
S = list(input())
ans = 0
i = 0
lst = ["A","C","G","T"]
while i < len(S) - 1:
    cnt = 0
    if S[i] in lst:
        cnt = 1
        for j in range(4):
            j += 1
            if not S[j] in lst:
                break
            cnt += 1
        ans = cnt
    i += 1
print(ans)

### FIXED CODE ###

S = list(input())
ans = 0
i = 0
cnt = 0
lst = ["A","C","G","T"]
for c in S:
    if c in lst:
        cnt += 1
    else:
        if ans < cnt:
            ans = cnt
        cnt = 0
if ans < cnt:
    ans = cnt
print(ans)
n, m = map(int, input().split())
prefers = [list(reversed(list(map(int, input().split())))) for _ in range(n)]
items = [True] * (m + 1)
competes = {i: 0 for i in range(1, m + 1)}
persons = [set() for _ in range(m + 1)]

for i, ps in enumerate(prefers):
    item = ps[-1]
    competes[item] += 1
    persons[item].add(i)

ans = m
remain = m
while ans > m // remain:
    mx = max(competes.values())
    ans = min(ans, mx)
    del_items = [a for a, k in competes.items() if k == mx]
    for a in del_items:
        items[a] = False
        del competes[a]
    for a in del_items:
        pa = persons[a]
        try:
            for p in pa:
                pf = prefers[p]
                while not items[pf[-1]]:
                    pf.pop()
                item = pf[-1]
                persons[item].add(p)
                competes[item] += 1
        except:
            break
    remain -= 1

print(ans)


### FIXED CODE ###

from collections import defaultdict
from operator import itemgetter


def sub(prefers, canceled):
    res = defaultdict(int)
    for pref in prefers:
        p = pref[-1]
        while p in canceled:
            pref.pop()
            p = pref[-1]
        res[p] += 1

    return max(res.items(), key=itemgetter(1))


def solve(m, prefers):
    canceled = set()
    ans = float('inf')
    for _ in range(m):
        s, c = sub(prefers, canceled)
        canceled.add(s)
        ans = min(ans, c)
    return ans


n, m = map(int, input().split())
prefers = [list(reversed(list(map(int, input().split())))) for _ in range(n)]

print(solve(m, prefers))
N,K=map(int,input().split())

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

distance_dict=[[x,abs(x)] for x in candls]

for x in range(0,N):
  if candls[x]>=0:
    x-=1
    break

resultlist=[]
minus=x
if K==1:
  print (min(candls[minus],candls[minus+1]))
  exit()
elif minus==-1:
  print(candls[K-1])
  exit()
elif minus-K+1>=0:
  resultlist.append(abs(candls[minus-K+1]))
  for i in range(1,2*K):
    try:
      resultlist.append(abs(candls[minus+i])+abs(candls[minus-K+1+i])+min(candls[minus+i],abs(candls[minus-K+1+i])))
    except:
      break
else:
  for i in range(1,minus+2):
    try:
      resultlist.append(abs(candls[K-1+i])+abs(candls[0+i])+min(candls[K-1+i],abs(candls[0+i])))
    except:
      break
try:
  resultlist.append(candls[minus+K])
except:
  pass

print (min(resultlist))

### FIXED CODE ###

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

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

distance_dict=[[x,abs(x)] for x in candls]

for x in range(0,N):
  if candls[x]>=0:
    x-=1
    break

resultlist=[]
minus=x
if K==1:
  print (min(abs(candls[minus]),abs(candls[minus+1])))
  exit()
elif minus==-1:
  print(abs(candls[K-1]))
  exit()
elif minus-K+1>=0:
  resultlist.append(abs(candls[minus-K+1]))
  for i in range(1,2*K):
    try:
      resultlist.append(abs(candls[minus+i])+abs(candls[minus-K+1+i])+min(candls[minus+i],abs(candls[minus-K+1+i])))
    except:
      break
else:
  for i in range(0,minus+2):
    try:
      resultlist.append(abs(candls[K-1+i])+abs(candls[0+i])+min(candls[K-1+i],abs(candls[0+i])))
    except:
      break
try:
  resultlist.append(candls[minus+K])
except:
  pass

print (min(resultlist))
N,M = map(int,input().split())

par = [i for i in range(N+M)]
def root(a):
    if par[a] == a: return a
    return root(par[a])

def same(a,b):
    return root(a) == root(b)

def unite(a,b):
   ra,rb = root(a),root(b)
   if ra == rb: return
   par[ra] = rb

for i in range(N):
    src = list(map(lambda x:int(x)-1,input().split()))
    for j in src[1:]:
        unite(i,N+j)

for i in range(1,N):
    if not same(0,i):
        print('NO')
        exit()
print('YES')

### FIXED CODE ###

import sys
sys.setrecursionlimit(2 * 10**5)
N,M = map(int,input().split())

par = [i for i in range(N+M)]
def root(a):
    if par[a] == a: return a
    par[a] = root(par[a])
    return par[a]

def same(a,b):
    return root(a) == root(b)

def unite(a,b):
   ra,rb = root(a),root(b)
   if ra == rb: return
   par[ra] = rb

for i in range(N):
    src = list(map(lambda x:int(x)-1,input().split()))
    if len(src) == 1: continue
    for j in src[1:]:
        unite(i,N+j)

for i in range(1,N):
    if not same(0,i):
        print('NO')
        exit()
print('YES')
S = list(input())
if S[0] == S[1] == S[2]:
  print("Yes)
else:
  print("No")

### FIXED CODE ###

S = list(input())
if S[0] == S[1] == S[2]:
  print("No")
else:
  print("Yes")
n,m = map(int,input().split())
s=[int(input()) for i in range(m)]
l=[1]
if s[0]!= 1:l.append(1)
else:l.append(0)
for i in range(2,n+1):
    if i in s:num=0
    else:num = (l[i-2]+l[i-1])%1000000007
    l.append(num)
print(l[-1])

### FIXED CODE ###

n,m = map(int,input().split())
s=set([int(input()) for i in range(m)])
l=[1]+[0]*n
INF=1000000007
if n ==1:
    print(1)
    exit()
if len(s)!=0 and 1 in s:l[1]=0
else:l[1]=1
for i in range(2,n+1):
    if i in s: l[i]=0
    else:l[i] = (l[i-2]+l[i-1])%INF
print(l[-1])
# coding: UTF-8
import os

def remove_empty(target_list: list):
    empty_removed_list = [x for x in target_list if x]
    return empty_removed_list

def get_stdin_str_list():
    input_str = input().strip()
    input_str_list = input_str.split()
    return input_str_list

def get_stdin_int_list():
    input_str_list = get_stdin_str_list()
    input_int_list = list(map(input_str_list, int))
    return input_int_list


S = get_stdin_str_list()
if S[2] == S[3] and S[4] == S[5]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

# coding: UTF-8
import os

def remove_empty(target_list: list):
    empty_removed_list = [x for x in target_list if x]
    return empty_removed_list

def get_stdin_str_list():
    input_str = input().strip()
    input_str_list = input_str.split()
    return input_str_list

def get_stdin_int_list():
    input_str_list = get_stdin_str_list()
    input_int_list = list(map(input_str_list, int))
    return input_int_list


S = get_stdin_str_list()[0]
if S[2] == S[3] and S[4] == S[5]:
    print("Yes")
else:
    print("No")
n, m = list(map(int, input().split()))
ac = set()
wa = 0
for i in range(m):
  p, s = input.split()
  p = int(p)
  if p in ac:
    continue
  if s == 'WA':
    wa += 1
  else:
    ac.add(p)
print("%d %d" % (len(ac), wa))

### FIXED CODE ###

n, m = list(map(int, input().split()))
ac = set()
wa = {}
for i in range(m):
  p, s = input().split()
  p = int(p)
  if p in ac:
    continue
  if s == 'WA':
    wa[p] = wa.get(p, 0) + 1
  else:
    ac.add(p)
pe = 0
for p in set(ac) & set(wa.keys()):
    pe += wa[p]
print("%d %d" % (len(ac), pe))
import numpy as np

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

a = np.array(A)
l = int(((N**2)+1)/2)
b = np.tile((1,-1),(1,l))
c = np.delete(b, 2*l-1, axis=None)
d = c.reshape(N,N)
e = np.triu(d)
f = np.tril(d)
g = np.eye(N)

inv = 0.5*(e-(f-g))

x = 2*(np.dot(inv,a))

ans = list(map(str, list(map(int, list(x)))))
print(" ".join(ans))

### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
a = np.array(A)
# l = int(((N*N)+1)/2)
b = []
for i in range(N):
    if i%2==0:
        b.append(1)
    else:
        b.append(-1)
c = np.dot(np.array(b),a)
x = [c]
for j in range(1,N):
    x_j = 2*a[j-1] - x[j-1]
    x.append(x_j)
ans = list(map(str, list(map(int, list(x)))))
print(" ".join(ans))
N,K=map(int,input().split())
A=sorted(list(map(int,input().split())))
if K==0:print(max(A));exit()

left,right=0,10**9+1
while right>left+1:
    cnt=K
    mid=(left+right)//2
    for i in range(N):
        cnt -=A[i]//mid
    if cnt>=0:right=mid
    elif cnt<0:left=mid

cnt=K
for i in range(N):
    cnt -=A[i]//left
print(left if cnt==0 else right)

### FIXED CODE ###

from math import ceil
N,K=map(int,input().split())
A=sorted(list(map(int,input().split())))
if K==0:print(max(A));exit()

left,right=0,10**9+1
while right>left+1:
    cnt=K
    mid=(left+right)//2
    for i in range(N):
        cnt -=ceil(A[i]/mid)-1
    if cnt>=0:right=mid
    elif cnt<0:left=mid

print(right)