Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import deque


def main():
    N, M = map(int, input().split())
    edges = [[] for _ in range(N)]

    for _ in range(M):
        u, v = map(int, input().split())
        edges[u - 1].append(v - 1)

    converted_edges = [[] for _ in range(N)]
    for v, v_edge in enumerate(edges):
        three_steps_nodes = []
        for w in edges[v]:
            for x in edges[w]:
                for y in edges[x]:
                    three_steps_nodes.append(y)
        converted_edges[v] = three_steps_nodes[:]

    S, T = map(lambda x: int(x) - 1, input().split())
    q = deque([(S, 0)])

    nodes = [-1] * N

    while q:
        cv, count = q.popleft()
        if cv == T:
            if nodes[cv] == -1:
                nodes[cv] = count
            else:
                nodes[cv] = min(nodes[cv], count)
        else:
            if nodes[cv] == -1 or count < nodes[cv]:
                nodes[cv] = count
                for u in converted_edges[cv]:
                    q.append((u, count + 1))

    print(nodes[T])


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque


def main():
    N, M = map(int, input().split())
    edges = [[] for _ in range(3 * N)]

    for _ in range(M):
        u, v = map(lambda x: int(x) - 1, input().split())
        edges[3 * u].append(3 * v + 1)
        edges[3 * u + 1].append(3 * v + 2)
        edges[3 * u + 2].append(3 * v)

    S, T = map(lambda x: (int(x) - 1) * 3, input().split())
    q = deque([(S, 0)])
    nodes = [-1] * (3 * N)

    while q:
        cv, count = q.popleft()

        if cv == T:
            nodes[cv] = count if nodes[cv] == -1 else min(nodes[cv], count)
        else:
            if nodes[cv] == -1 or count < nodes[cv]:
                nodes[cv] = count
                for u in edges[cv]:
                    q.append((u, count + 1))

    print(nodes[T] // 3 if nodes[cv] != -1 else -1)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

S = input()
Q = int(input())
L = [list(input().split()) for i in range(Q)]

hanten = 0
t = [S]
for l in L:
    if len(l) == 1:
        hanten += 1
    elif (l[1] == '1' and hanten % 2 == 0) or (l[1] == '2' and hanten % 2 == 1):
        t.insert(0, l[2])
    else:
        t.append(l[2])
ans = ''.join(t)
if hanten % 2 == 1:
    ans = ''.join(list(reversed(ans)))
print(ans)

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())
L = [list(input().split()) for i in range(Q)]

hanten = 0
t = deque([S])

for l in L:
    if len(l) == 1:
        hanten += 1
    elif (l[1] == '1' and hanten % 2 == 0) or (l[1] == '2' and hanten % 2 == 1):
        t.appendleft(l[2])
    else:
        t.append(l[2])

ans = ''.join(t)
if hanten % 2 == 1:
    ans = ''.join(list(reversed(ans)))
print(ans)
### BUGGY CODE ###

import sys,heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def coco():
    n = onem()

    a = l()

    b = l()

    t = []

    for i in range(n):
        if b[i] != a[i]:
            hq.heappush(t,[-b[i],i])
    co = 0
    while t:
        k = hq.heappop(t)
        k = [-k[0],k[1]]
        if k[1] == 0:
            ppp = (k[0]-a[k[1]]) // (b[-1] + b[1])
            if ppp == 0:
                return -1
                
            co += ppp
            k[0] = (k[0]-a[k[1]]) % (b[-1] + b[1]) + a[k[1]]
        elif k[1] == n-1:
            ppp = (k[0]-a[k[1]]) // (b[-2] + b[0])
            if ppp == 0:
                return -1
            co += ppp
            k[0] = (k[0]-a[k[1]]) % (b[-2] + b[0]) + a[k[1]]
        else:
            ppp = (k[0]-a[k[1]]) // (b[k[1]+1] + b[k[1]-1])
            if ppp == 0:
                return -1
            co += ppp
            k[0] = (k[0]-a[k[1]]) % (b[k[1]+1] + b[k[1]-1]) + a[k[1]]
        b[k[1]] = k[0]
        if b[k[1]] != a[k[1]]:
            hq.heappush(t,[-b[k[1]],k[1]])
    return co

print(coco())


### FIXED CODE ###

import heapq as hq
mod = 10**9+7
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())

def onon():
    n = onem()

    a = l()

    b = l()

    t = []

    for i in range(n):
        if b[i] != a[i]:
            hq.heappush(t,(-b[i],i))
    co = 0
    while t:
        k = hq.heappop(t)
        k = (-k[0],k[1])
        q,w = divmod(k[0] - a[k[1]], b[(k[1] - 1) % n] + b[(k[1] + 1) % n])
        co += q
        if q == 0:
            return -1
        w = a[k[1]] + w
        b[k[1]] = w
        if b[k[1]] != a[k[1]]:
            hq.heappush(t,(-w,k[1]))
    return co
print(onon())
### BUGGY CODE ###

n,m=list(map(int, input().split()))
h=list(map(int, input().split()))
p=[]
remain = set(range(1, n+1))
for i in range(m):
    p.append(list(map(int, input().split())))
#p.sort()
temp = []
for a,b in p:
    temp.append([b,a])
p = p + temp
#p.sort()
for a,b in p:
    if not (a in remain):
        continue
    if h[a-1]<=h[b-1]:
        remain = remain - set([a])
print(len(remain))

### FIXED CODE ###

n,m=list(map(int, input().split()))
h=list(map(int, input().split()))
p=[]
remain = set(range(1, n+1))
for i in range(m):
    p.append(list(map(int, input().split())))
temp = []
for a,b in p:
    temp.append([b,a])
p = p + temp
delset = set()
for a,b in p:
    if h[a-1]<=h[b-1]:
        #remain = remain - set([a])
        delset.add(a)
remain = remain - delset
print(len(remain))
### BUGGY CODE ###

#頂点を見た時に，枝分かれの本数に応じてansを更新

import sys
input = sys.stdin.readline

mod=10**9+7

def permu(a,b):
    c=1
    for i in range(b):
        c*=(a-i)
    return c

N,K=map(int,input().split())
adj=[[] for _ in range(N)]

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

q=[(0,-1,0)]#node,parent,depth

ans=1
while q!=[]:
    v,p,d=q.pop()
    #K2やPは，深さ0or1で若干異なる
    K2=max(K-2,K-d-1)
    l=len(adj[v])
    P=permu(K2,max(l-d,l-1))
    ans*=P
    ans%=mod
    for i in range(l):
        next_v=adj[v][i]
        #葉は追加しない
        if next_v!=p and len(adj[next_v])!=1:
            q.append((next_v,v,d+1))

print((ans*K)%mod)

### FIXED CODE ###

#頂点を見た時に，枝分かれの本数に応じてansを更新
#permutationのリストを先に作っておく

import sys
input = sys.stdin.readline

mod=10**9+7


N,K=map(int,input().split())
ab=[list(map(int, input().split())) for _ in range(N - 1)]
adj=[[] for _ in range(N)]

for a,b in ab:
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)
    
    
#順列(K-2)Piを先に
P=[1]
for i in range(N):
    P.append((P[-1]*(K-2-i))%mod)
    

q=[(0,-1,0)]#node,parent,depth

ans=1
while q!=[]:
    v,p,d=q.pop()
    #深さ0or1で塗ることができる色数は異なる
    l=len(adj[v])
    if d==0:
        ans*=(K-1)
    ans*=(P[l-1])
    ans%=mod
    for i in range(l):
        next_v=adj[v][i]
        #葉は追加しない
        if next_v!=p and len(adj[next_v])!=1:
            q.append((next_v,v,d+1))
if N==1:
    ans=1
print((ans*K)%mod)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
T = int(input())
for _ in range(T):
	n, a, b, c, d = map(int, input().split())
#	ans = 10**20
#	for i in range(61):
#		for j in range(39):
#			if pow(2, i) * pow(3, j) > 10**19:
#				continue
#			for k in range(27):
#				if pow(2, i) * pow(3, j) * pow(5, k) > 10**19:
#					continue
#				for l in range(1, 6):
#					g = abs(n - l * pow(2, i) * pow(3, j) * pow(5, k))
#					res = a*i + b*j + c*k + (g+l) * d
#					ans = min(ans, res)
#	print(ans)
	dp = dict()
	dp[n] = 0

	def add(x, v):
		if x not in dp:
			dp[x] = v
			return True
		elif dp[x] > v:
			dp[x] = v
			return True
		else:
			return False

	def dfs(x):
		if x == 0:
			return
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
			v = min(a+d, d + d*(x//2+1)) + dp[x]
			if add((x+1)//2, v):
				dfs((x+1)//2)

		if x%3 == 0:
			v = min(b, d*2*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
		else:
			m = x%3
			v = min(b+d*m, d*m + d*2*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
			v = min(b+d*(3-m), d*(3-m) + d*2*(x//3 + 1)) + dp[x]
			if add(x//3+1, v):
				dfs(x//3+1)

		if x%5 == 0:
			v = min(c, d*4*(x//5)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
		else:
			m = x%5
			v = min(c+d*m, d*m + d*4*(x//4)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
			v = min(c+d*(5-m), d*(5-m) + d*4*(x//4 + 1)) + dp[x]
			if add(x//5+1, v):
				dfs(x//5+1)
		return
	dfs(n)
	print(dp[0])

### FIXED CODE ###

import sys
from heapq import heappush, heappop
T = int(input())
for _ in range(T):
	n, a, b, c, d = map(int, input().split())
	dp = dict()
	dp[n] = 0
	q = [(0, n)]
	def add(x, v):
		if x not in dp:
			dp[x] = v
			return True
		elif dp[x] > v:
			dp[x] = v
			return True
		else:
			return False

	while True:
		l = heappop(q)
		if l[1] == 0:
			break
		x = l[1]
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				heappush(q, (v, x//2))
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				heappush(q, (v, x//2))
			v = min(a+d, d + d*(x//2+1)) + dp[x]
			if add(x//2+1, v):
				heappush(q, (v, x//2+1))

		if x%3 == 0:
			v = min(b, d*2*(x//3)) + dp[x]
			if add(x//3, v):
				heappush(q, (v, x//3))
		else:
			m = x%3
			v = min(b+d*m, d*m + d*2*(x//3)) + dp[x]
			if add(x//3, v):
				heappush(q, (v, x//3))
			v = min(b+d*(3-m), d*(3-m) + d*2*(x//3 + 1)) + dp[x]
			if add(x//3+1, v):
				heappush(q, (v, x//3+1))

		if x%5 == 0:
			v = min(c, d*4*(x//5)) + dp[x]
			if add(x//5, v):
				heappush(q, (v, x//5))
		else:
			m = x%5
			v = min(c+d*m, d*m + d*4*(x//5)) + dp[x]
			if add(x//5, v):
				heappush(q, (v, x//5))
			v = min(c+d*(5-m), d*(5-m) + d*4*(x//5 + 1)) + dp[x]
			if add(x//5+1, v):
				heappush(q, (v, x//5+1))

	print(dp[0])
### BUGGY CODE ###

h,n=map(int,input().split())
M=[list(map(int,input().split())) for _ in range(n)]
dp = [[-(-i//M[0][0])*M[0][1] for i in range(1,h+1)] for _ in range(n)]
for i in range(1,n):
  for j in range(h):
    if j<M[i][0]:
      dp[i][j]=min(dp[i-1][j],M[i][1])
    else:
      dp[i][j]=min(dp[i-1][j],dp[i][j-M[i][0]]+M[i][1])
print(dp[n-1][h-1])

### FIXED CODE ###

h,n=map(int,input().split())
M=[list(map(int,input().split())) for _ in range(n)]
dp = [[-(-i//M[0][0])*M[0][1] for i in range(1,h+1)] for _ in range(n)]
for i in range(1,n):
  for j in range(h):
    if j<M[i][0]:
      dp[i][j]=min(dp[i-1][j],M[i][1])
    else:
      dp[i][j]=min(dp[i-1][j],dp[i][j-M[i][0]]+M[i][1])
print(dp[n-1][h-1])
### BUGGY CODE ###

n = int(input())
s = input()
q = int(input())
for i in range(q):
	a,b,c=map(str, input().split())
	if a=="1":
		s=s[:int(b)-1]+c+s[int(b):]
	if a=="2":
		print(len(set(s[int(b)-1:int(c)])))

### FIXED CODE ###

n = int(input())
stmp = list(input())
Q = int(input())
target = ord("a")
s = [ord(stmp[i])-target for i in range(n)]

class BIT:
	"""
	<Attention> 0-indexed.
	query ... return the sum [0 to m]
	sum ... return the sum [a to b]
	sumall ... return the sum [all]
	add ... 'add' number to element (be careful that it doesn't set a value.)
	search ... the sum version of bisect.right
	output ... return the n-th element
	listout ... return the BIT list
	"""
	
	def query(self, m):
		res = 0
		while m > 0:
			res += self.bit[m]
			m -= m&(-m)
		return res
	
	def sum(self, a, b):
		return self.query(b)-self.query(a)
	
	def sumall(self):
		bitlen = self.bitlen-1
		return self.query(bitlen)
	
	def add(self, m, x):
		m += 1
		bitlen = len(self.bit)
		while m <= bitlen-1:
			self.bit[m] += x
			m += m&(-m)
		return
	
	def __init__(self, n):
		self.bitlen = n+1
		self.bit = [0]*(n+1)

b = [BIT(n) for i in range(26)]
for i in range(n):
	b[s[i]].add(i, 1)

for _ in range(Q):
	q,qtmpa,qtmpb = input().split()
	if q[0] == "1":
		qa = int(qtmpa)
		t = ord(qtmpb)-target
		b[t].add(qa-1, 1)
		b[s[qa-1]].add(qa-1, -1)
		s[qa-1] = t
	else:
		ans = 0
		qta = int(qtmpa)
		qtb = int(qtmpb)
		for i in range(26):
			if b[i].sum(qta-1, qtb) != 0:
				ans += 1
		print(ans)
### BUGGY CODE ###

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

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)


if n == 2:
    print(max(a))
else:
    cand = []
    for j in range(n):
        if j == 0:
            temp = a[1]
            for i in range(2,len(a)):
                temp = gcd(temp, a[i])
        else:
            temp = a[0]
            for i in range(1,len(a)):
                if i != j:
                    temp = gcd(temp, a[i])
        cand.append(temp)
    print(max(cand))


### FIXED CODE ###

# -*- coding: utf-8 -*-

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

if n == 2:
    print(max(a))
else:
    list1 = make_divisors(a[0])
    list2 = make_divisors(a[1])
    list1.sort()
    list2.sort()
    flag1 = 0
    cand1 = 0
    for i in range(len(list1)):
        flag1 = 0
        for j in range(n):
            if a[j] % list1[i] != 0:
                flag1 += 1
        if flag1 <= 1:
            cand1 = list1[i]
    cand2 = 0
    for i in range(len(list2)):
        flag2 = 0
        for j in range(n):
            if a[j] % list2[i] != 0:
                flag2 += 1
        if flag2 <= 1:
            cand2 = list2[i]
    print(max(cand1,cand2))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
LR = [list(map(int, input().split())) for _ in range(Q)]

for lr in LR:
    l, r = lr[0], lr[1]
    s = S[l-1: r]
    i = s.count("AC")
    print(i)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
LR = [list(map(int, input().split())) for _ in range(Q)]

t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)

for i in range(Q):
    l, r = LR[i][0], LR[i][1]
    cnt = t[r - 1] - t[l -1]
    print(cnt)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
dp=[0]*(n+1)
dp[0]=1
if 1 in a:
    dp[1]=0
else:
    dp[1]=1
for i in range(2,n+1):
    if i in a:
        dp[i]=0
    else:
        dp[i]=dp[i-1]+dp[i-2]
print(dp[n]%1000000007)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
b=[]
for i in range(m):
    b.append(int(input()))
a=set(b)
dp=[0]*(n+1)
dp[0]=1
if 1 in a:
    dp[1]=0
else:
    dp[1]=1
for i in range(2,n+1):
    if i in a:
        dp[i]=0
    else:
        dp[i]=dp[i-1]+dp[i-2]
print(dp[n]%1000000007)
### BUGGY CODE ###

n = int(input())
a = list(input().split())
ans = a[0]
for i in range(n):
	if i%2 == 0 and i != 0:
		ans = ans + ' ' + a[i]
	elif i%2 != 0:
		ans = a[i] + ' ' + ans
if n%2 != 0 and n != 1:
	print(ans[::-1])
else:
	print(ans)

### FIXED CODE ###

n = int(input())
a = list(input().split())
a1 = ['']*(n//2 + n%2)
a2 = ['']*(n//2)

for i in range(n):
	if i%2 == 0:
		a1[i//2] = a[i]
	else:
		a2[-i//2] = a[i]

if n%2 != 0 and n != 1:
	ans = ' '.join(a1[::-1]) + ' ' + ' '.join(a2[::-1])
elif n%2 == 0:
	ans = ' '.join(a2) + ' ' + ' '.join(a1)
else:
	ans = a[0]
print(ans)
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
    a.append(int(input()) - 1)

visited = [False] * n
f = 0
cnt = 0
visited[f] = True
flg = True
while True:
    t = a[f]
    if visited[t]:
        flg = False
        break
    cnt += 1
    if t == 1:
        break
    f = t
print(cnt) if flg else print(-1)

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
    a.append(int(input()) - 1)

visited = [False] * n
f = 0
visited[f] = True
cnt = 0
while True:
    cnt += 1
    t = a[f]
    if t == 1:
        flg = True
        break
    if visited[t]:
        flg = False
        break
    visited[t] = True
    f = t
print(cnt) if flg else print(-1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N,M = list(map(int,input().split()))

res_dict = {0:0}
for _ in range(N):
    #M本になるまでは買い続け、M本より多くなった場合は、価格の高いものから
    a,b = list(map(int,input().split()))
    cur_max_price = max(res_dict.keys())
    if sum(res_dict.values()) - M < 0 or a < cur_max_price:
        #追加操作
        if a in res_dict:
            res_dict[a] += b
        else:
            res_dict[a] = b
    decrease = sum(res_dict.values()) - M
    while decrease > 0:
        max_price = max(res_dict.keys())
        if decrease < res_dict[max_price]:
            res_dict[max_price] -= decrease
            break
        else:
            decrease -= res_dict[max_price]
            res_dict.pop(max_price)

print(sum([k * v for k,v in res_dict.items()]))


### FIXED CODE ###

# -*- coding: utf-8 -*-
N,M = list(map(int,input().split()))

l = [list(map(int,input().split())) for _ in range(N)]
l = sorted(l, key=lambda x:x[0])
a_cnt = 0
b_cnt = 0
for a,b in l:
    if b <= M:
        b_cnt += b
        M -= b
        a_cnt += a*b
    elif b > M and M > 0:
        b_cnt += M
        a_cnt += a*M
        break
    else:
        break
print(a_cnt)
### BUGGY CODE ###

import copy as cp

N,M = map(int,input().split())
P = []
Y = []
for i in range(M):
    p,y = map(int,input().split())
    P.append(p)
    Y.append(y)
#print(N,M,P,Y)

C_lst = [[] for _ in range(N)]
for i in range(M):
    C_lst[P[i]-1].append(Y[i])
#print(N,M,P,Y,C_lst)
C_cp = cp.deepcopy(C_lst)
for i in range(N):
    C_cp[i].sort()
for i in range(M):
    ans = "0"*(6-len(str(P[i]))) + str(P[i])
    idx = C_cp[P[i]-1].index(Y[i]) + 1
    ans += "0"*(6-len(str(idx))) + str(idx)
    print(ans)

### FIXED CODE ###

import copy as cp

def bin_search(n,lst):
    l=0
    r=len(lst)
    
    while r-1>=l:
        i=(l+r)//2
        if lst[i]==n: return i
        elif lst[i]<n: l=i+1
        else: r=i

N,M = map(int,input().split())
P = []
Y = []
for i in range(M):
    p,y = map(int,input().split())
    P.append(p)
    Y.append(y)
#print(N,M,P,Y)

C_lst = [[] for _ in range(N)]
for i in range(M):
    C_lst[P[i]-1].append(Y[i])
#print(N,M,P,Y,C_lst)
C_cp = cp.deepcopy(C_lst)
for i in range(N):
    C_cp[i].sort()
for i in range(M):
    ans = "0"*(6-len(str(P[i]))) + str(P[i])
    idx = bin_search(Y[i],C_cp[P[i]-1]) + 1
    ans += "0"*(6-len(str(idx))) + str(idx)
    print(ans)
### BUGGY CODE ###

Ns,Ms=input().split()
N=int(Ns)
M=int(Ms)
LR=input().split()
ans=set(list(range(int(LR[0]),int(LR[1])+1)))
for i in range(M-1):
	LR=[]
	LR=input().split()
#	print("ssssssssss")
#	print(ans)
	ansy=set(list(range(int(LR[0]),(int(LR[1])+1))))
	ans=ans&ansy
ansx=list(ans)
print(len(ansx))


### FIXED CODE ###

Ns,Ms=input().split()
N=int(Ns)
M=int(Ms)
lists=[]
ansmins,ansmaxs=input().split()
ansmin=int(ansmins)
ansmax=int(ansmaxs)
for i in range(M-1):
	tmpmin,tmpmax=input().split()
	if int(tmpmin)>ansmin:
		ansmin=int(tmpmin)
	if int(tmpmax)<ansmax:
		ansmax=int(tmpmax)

if (ansmax-ansmin+1)<0:
	ans=0
else:
	ans=ansmax-ansmin+1
print(ans)
### BUGGY CODE ###

h,w = map(int,input().split())
field = [list(input()) for i in range(h)]

max_light = 0
for i in range(h):
    for j in range(w):
        n_light = 1
        if field[i][j] == '#':
            continue
        
        c = 1
        while True:
            if (j+c > w-1) or (j+c < 0) or (field[i][j+c] == '#'):
                break
            
            else:
                n_light += 1
                c += 1
        
        c = 1
        while True:
            if (j-c > w-1) or (j-c < 0) or (field[i][j-c] == '#'):
                break
            
            else:
                n_light += 1
                c += 1
        
        c = 1
        while True:
            if (i+c > h-1) or (i+c < 0) or (field[i+c][j] == '#'):
                break
            
            else:
                n_light += 1
                c += 1
        
        c = 1
        while True:
            if (i-c > h-1) or (i-c < 0) or (field[i-c][j] == '#'):
                break
            
            else:
                n_light += 1
                c += 1
        
        max_light = max(max_light,n_light)


print(max_light)

### FIXED CODE ###

h,w = map(int,input().split())
field = [list(input()) for i in range(h)]

l = [[0]*w for i in range(h)]
r = [[0]*w for i in range(h)] 
u = [[0]*w for i in range(h)] 
d = [[0]*w for i in range(h)] 

for i in range(h):
    for j in range(w):
        if field[i][j] == "#":
            l[i][j] = 0
        
        elif j == 0:
            l[i][j] = 1
        
        else:
            l[i][j] = l[i][j-1] + 1

for i in range(h):
    for j in range(w)[::-1]:
        if field[i][j] == "#":
            r[i][j] = 0
        
        elif j == w-1:
            r[i][j] = 1
        
        else:
            r[i][j] = r[i][j+1] + 1

for j in range(w):
    for i in range(h):
        if field[i][j] == "#":
            d[i][j] = 0
        
        elif i == 0:
            d[i][j] = 1
        
        else:
            d[i][j] = d[i-1][j] + 1
    
for j in range(w):
    for i in range(h)[::-1]:
        if field[i][j] == "#":
            u[i][j] = 0
        
        elif i == h-1:
            u[i][j] = 1
        
        else:
            u[i][j] = u[i+1][j] + 1
        
max_light = 0       
for i in range(h):
    for j in range(w):
        n_light = l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3
        
        max_light = max(max_light,n_light)

print(max_light)
### BUGGY CODE ###

# coding: utf-8
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def f2(n):
    dp = [[0] * n for _ in range(n)]
    s = [1] * n

    def dfs(i, j):  # from i to j
        dpi = dp[i]
        if dpi[j]:
            return(dpi[j])
        dpij = 1
        for u in U[i]:
            if u != j:
                dpij = dpij * (dfs(u, i) + 1) % M
        s[j] = s[j] * (dpij + 1) % M
        dpi[j] = dpij
        return(dpij)

    for i in range(n):
        for u in U[i]:
            dfs(u, i)
    print("\n".join([str(x) for x in s]))

N, M = map(int, input().split()) # 1 <= N <= 10^5, 2 <= M <= 10^9
U = [set() for _ in range(N)]
for x, y in [map(int, input().split()) for _ in range(N - 1)]:
    U[x - 1].add(y - 1)
    U[y - 1].add(x - 1)
f2(N)


### FIXED CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(v, p = -1):
    deg[v] = len(U[v])
    dp[v] = [0] * deg[v]
    ans = 1
    for i in range(deg[v]):
        u = U[v][i]
        if u == p:
            par[v] = i
            continue
        dp[v][i] = dfs(u, v)
        ans *= dp[v][i] + 1
        ans %= M
    return(ans)

def bfs(v, ans_p = 0, p = -1):
    if p != -1:
        dp[v][par[v]] = ans_p
    lmul = [1] * (deg[v] + 1)
    rmul = [1] * (deg[v] + 1)
    for i in range(1, deg[v] + 1):
        lmul[i] = lmul[i - 1] * (dp[v][i - 1] + 1) % M
        rmul[-i - 1] = rmul[-i] * (dp[v][-i] + 1) % M
    ans[v] = rmul[0]
    for i in range(deg[v]):
        u = U[v][i]
        if u == p:
            continue
        bfs(u, lmul[i] * rmul[i + 1] % M, v)

N, M = map(int, input().split()) # 1 <= N <= 10^5, 2 <= M <= 10^9
U = [list() for _ in range(N)]
for x, y in [map(int, input().split()) for _ in range(N - 1)]:
    U[x - 1].append(y - 1)
    U[y - 1].append(x - 1)
deg = [0] * N
par = [0] * N
dp = [None] * N
ans = [0] * N
dfs(0)
bfs(0)
print("\n".join([str(x) for x in ans]))
### BUGGY CODE ###

n=input()
a=list(map(int,input().split()))
a.sort()
#print(a)
i=0
ans=0
while i!=len(a):
    x=a[i]
    x1=a.count(x)
    if x<x1:
        ans=ans+x1-x
    elif x>x1:
        ans=ans+x1
    else:
        pass
    i=i+x1
print(ans)

### FIXED CODE ###

n=input()
a=list(map(int,input().split()))
a.sort()
#print(a)
i=0
ans=0
while i!=len(a):
    x=a[i]
    x1=a.count(x)
    if (x>len(a)-i):
        ans=ans+len(a)-i
        break
    else:

        if x<x1:
            ans=ans+x1-x
        elif x>x1:
            ans=ans+x1
        else:
            pass
        i=i+x1
print(ans)