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

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from heapq import heappush,heappop,heapify
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
X,Y=[0]*N,[0]*N
dx,dy=defaultdict(list),defaultdict(list)
for i in range(N):
    X[i],Y[i]=map(int,input().split())
    dx[X[i]].append(i)
    dy[Y[i]].append(i)
ux,uy=list(set(X)),list(set(Y))
ux.sort()
uy.sort()
uxi={x:i for i,x in enumerate(ux)}
uyi={y:i for i,y in enumerate(uy)}
edge=[[] for i in range(N)]
for i,(x,y) in enumerate(zip(X,Y)):
    for index in dx[x]+dy[y]:
        edge[i].append((0,index))
    if uxi[x]>=1:
        nx=ux[uxi[x]-1]
        for index in dx[nx]:
            if index!=i:
                edge[i].append((abs(nx-x),index))
    if uxi[x]<len(ux)-1:
        nx=ux[uxi[x]+1]
        for index in dx[nx]:
            if index!=i:
                edge[i].append((abs(nx-x),index))
    if uyi[y]>=1:
        ny=uy[uyi[y]-1]
        for index in dy[ny]:
            if index!=i:
                edge[i].append((abs(ny-y),index))
    if uyi[y]<len(uy)-1:
        ny=uy[uyi[y]+1]
        for index in dy[ny]:
            if index!=i:
                edge[i].append((abs(ny-y),index))

def prim(n,edges):
    used=[False]*n
    used[0]=True
    edgelist=[]
    for edge in edges[0]:
        heappush(edgelist,edge)
    cost=0
    while edgelist:
        minedge=heappop(edgelist)
        if used[minedge[1]]:
            continue
        v=minedge[1]
        used[v]=True
        for edge in edges[v]:
            if not used[edge[1]]:
                heappush(edgelist,edge)
        cost+=minedge[0]
    return cost

print(prim(N,edge))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from heapq import heappush,heappop,heapify
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
X,Y=[],[]
for i in range(N):
    x,y=map(int,input().split())
    X.append((y,i))
    Y.append((x,i))
X.sort(key=lambda t:t[0])
Y.sort(key=lambda t:t[0])
edge=[[] for i in range(N)]
for i in range(N-1):
    edge[X[i][1]].append((abs(X[i][0]-X[i+1][0]),X[i+1][1]))
    edge[X[i+1][1]].append((abs(X[i][0]-X[i+1][0]),X[i][1]))
    edge[Y[i][1]].append((abs(Y[i][0]-Y[i+1][0]),Y[i+1][1]))
    edge[Y[i+1][1]].append((abs(Y[i][0]-Y[i+1][0]),Y[i][1]))

def prim(n,edges):
    used=[False]*n
    used[0]=True
    edgelist=[]
    for edge in edges[0]:
        heappush(edgelist,edge)
    cost=0
    while edgelist:
        minedge=heappop(edgelist)
        if used[minedge[1]]:
            continue
        v=minedge[1]
        used[v]=True
        for edge in edges[v]:
            if not used[edge[1]]:
                heappush(edgelist,edge)
        cost+=minedge[0]
    return cost

print(prim(N,edge))
### BUGGY CODE ###

n = int(input())+1
a = list(map(int, input().split()))
cnt = []

sum = 0
for i in range(100005):
    cnt.append(a.count(i))
    sum += i * cnt[i]

q = int(input())

for i in range(q):
    b, c = map(int, input().split())
    sum += (c-b)*cnt[b]
    cnt[c] += cnt[b]
    cnt[b] = 0
    print(sum)


### FIXED CODE ###

n = int(input())+1
a = list(map(int, input().split()))
cnt = []
for i in range(100005):
    cnt.append(0)
sum = 0

for i in a:
    cnt[i] += 1
for i in range(100005):
    sum += i * cnt[i]

q = int(input())

for i in range(q):
    b, c = map(int, input().split())
    sum += (c-b)*cnt[b]
    cnt[c] += cnt[b]
    cnt[b] = 0
    print(sum)
### BUGGY CODE ###

n = int(input())
c = list(input())
sc = list(reversed(c))
ans = 0
r = 0
flg  = False

if 'W' not in set(c) or 'R' not in set(c):
    print(ans)


else:
    for i in range(n):
        if flg:
            break
        if c[i] == 'W':
            for j in range(r, n):
                if sc[j] == 'R':
                    if n >= i+j+2:
                        c[i] = 'R'
                        c[-1*j-1] = 'W'
                        ans += 1
                        sc = list(reversed(c))
                        break
                    else:
                        flg = True
                        break

                else:
                    r += 1
            

    print(ans)

### FIXED CODE ###

n = int(input())
c = list(input())
sc = list(reversed(c))
ans = 0
r = 0
flg  = False

if 'W' not in set(c) or 'R' not in set(c):
    print(ans)


else:
    for i in range(n):
        if flg:
            break
        if c[i] == 'W':
            for j in range(r, n):
                r += 1
                if sc[j] == 'R':
                    if n >= i+j+2:
                        c[i] = 'R'
                        c[-1*j-1] = 'W'
                        ans += 1
                        break
                    else:
                        flg = True
                        break

                
            

    print(ans)
### BUGGY CODE ###

n=int(input())

ans=0
for i in range(n):
      ans+=i
print(ans)
            

### FIXED CODE ###

n=int(input())

print(((n-1)*(n))//2)
### BUGGY CODE ###

from sys import stdin
n = int(stdin.readline().rstrip())
s = stdin.readline().rstrip()
point = 0
for i in range(1000):
    bango = str(i).zfill(3)
    count = 0
    for j in range(n):
        if s[j] == bango[count]:
            count += 1
        if count == 3:
            point += 1
            break
print(point)

### FIXED CODE ###

from sys import stdin
n = int(stdin.readline().rstrip())
s = stdin.readline().rstrip()

def count(poi):
    point = 0
    for i in range(poi):
        bango = str(i).zfill(3)
        count = 0
        for j in range(n):
            if s[j] == bango[count]:
                count += 1
            if count == 3:
                point += 1
                break
    return point

print(count(1000))
### BUGGY CODE ###

import copy

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

asum = [0]
bsum = [0]
tmp = 0
for i in range(n):
    tmp += a[i]
    asum.append(tmp)
tmp = 0
for i in range(m):
    tmp += b[i]
    bsum.append(tmp)


ans = 0
ms = copy.deepcopy(m)
for na in range(n+1):
    res = k - asum[na]
    if res < 0:
        break
    flg = True
    nb = copy.deepcopy(m)
    while flg:
        if bsum[nb] > res:
            nb -= 1
            continue
        ans = max(ans, na+nb)
        ms = copy.deepcopy(nb)
        break
print(ans)

### FIXED CODE ###

import copy

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

asum = [0]
bsum = [0]
tmp = 0
for i in range(n):
    tmp += a[i]
    asum.append(tmp)
tmp = 0
for i in range(m):
    tmp += b[i]
    bsum.append(tmp)


ans = 0
nb = copy.deepcopy(m)
for na in range(n+1):
    res = k - asum[na]
    if res < 0:
        break
    flg = True
    while flg:
        if bsum[nb] > res:
            nb -= 1
            continue
        ans = max(ans, na+nb)
        break
print(ans)
### BUGGY CODE ###

def main():
	import sys
	from operator import itemgetter
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		for z in [None]*Q:
			if e[0] > d:
				if cont == True:
					if mini < 1000000001:
						print(mini)
					else:
						print(-1)
				else:
					mini = min(kouho)
					if mini < 1000000001:
						print(mini)
					else:
						print(-1)
			else:
				break
			cont = True
			if q < Q-1:
				q = q + 1
				d = int(inputs())
			else:
				flag = True
				q = q + 1
				break
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			cont = False
	for t in [None]*(Q-q):
		print(-1)
main()

### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
line = input().split(" ")
N = int(line[0])
M = int(line[1])
Q = int(line[2])

memo = [[0 for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    line = input().split(" ")
    l = int(line[0])
    r = int(line[1])
    memo[l][r] += 1

for _ in range(Q):
    line = input().split(" ")
    p = int(line[0])
    q = int(line[1])

    ret = 0
    for i in range(p,q+1):
        for j in range(i,q+1):
            ret += memo[i][j]
    print(ret)


### FIXED CODE ###

# -*- coding: utf-8 -*-
n,m,q = map(int, input().split())

d = [[0 for _ in range(n+1)] for _ in range(n+1)]

for _ in range(m):
    l,r = map(int, input().split())
    d[l][r] += 1
for i in range(n,0,-1):
    for j in range(n):
        d[i][j+1] += d[i][j]
for j in range(n,0,-1):
    for i in range(n,0,-1):
        d[i-1][j] += d[i][j]

pq = []
for _ in range(q):
    p,q = map(int, input().split())
    pq.append([p,q])

# print(d)
for o in pq:
    print(d[o[0]][o[1]])
### BUGGY CODE ###

import numpy as np

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

def func(a):
  for i in range(q):
    b,c=map(int, input().split())
    a[a==b]=c
    print(np.sum(a))

func(a)

### FIXED CODE ###

import collections

N=int(input())
A=list(map(int,input().split()))
X=collections.Counter(A)
Q=int(input())

ans=sum(A)
for i in range(Q):
  B,C=map(int,input().split())
  ans+=(C-B)*X[B]
  print(ans)
  X[C]+=X[B]
  X[B]=0
### BUGGY CODE ###

def dfs(i, j, s):
    if j > 3:
        return
    if j == 3 and sum(s) == x:
        res.append(1)

    for k in range(1, i):
        if sum(s) + k > x:
            break
        if k not in s:
            dfs(k, j + 1, s + [k])

ans = []
while True:
    res = []
    n, x = map(int, input().split())
    if n == x == 0:
        break
    for i in range(3, n + 1):
        dfs(i, 1, [i])

    ans.append(sum(res))

print("\n".join(map(str, ans)))


### FIXED CODE ###

def calc(n, x):
    result = 0
    for i in range(3, n + 1):
        for j in range(2, i):
            if i + j < x < i + 2 * j:
                result += 1
    return str(result)

ans = []
while True:
    n, x = map(int, input().split())
    if n == x == 0:
        break
    ans.append(calc(n, x))

print("\n".join(ans))
### BUGGY CODE ###

import collections

n = int(input())
que = collections.deque()

for i in range(n):
    lineArr = input().split()
    ope = lineArr[0]

    if ope == 'insert':
        num = int(lineArr[1])
        que.insert(0, num)
    elif ope == 'delete':
        num = int(lineArr[1])
        try:
            que.remove(num)
        except ValueError:
            pass
    elif ope == 'deleteFirst':
        que.popleft()
    else:
        que.pop()

print(*que)



### FIXED CODE ###

import collections

n = int(input())
que = collections.deque()

for i in range(n):
    line = input()

    if line[0] == 'i':
        que.appendleft(int(line[7:]))
    elif line[6] == ' ':
        try:
            que.remove(int(line[7:]))
        except ValueError:
            pass
    elif line[6] == 'F':
        que.popleft()
    else:
        que.pop()

print(*que)
### BUGGY CODE ###

#bfs2-AGC033A
h,w=map(int,input().split())
s=[input() for _ in range(h)]

sxy=[]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            sxy.append([i,j])
ddx=[1,-1,0,0]
ddy=[0,0,1,-1]

t=[[-1 for _ in range(w)] for _ in range(h)]
q=[]
for txy in sxy:
    q.append(txy)
    t[txy[0]][txy[1]]=0

count=0
while q:
    y,x=q.pop(0)
    count+=1
    for (dx,dy) in zip(ddx,ddy):
        ny=y+dy
        nx=x+dx
        if not (0<=nx<w and 0<=ny<h):continue
        if t[ny][nx]==-1:
            t[ny][nx]=t[y][x]+1
            q.append([ny,nx])
a=0
for i in range(h):
    for j in range(w):
        a=max(a,t[i][j])
print(a)

### FIXED CODE ###

#bfs2-AGC033A
h,w=map(int,input().split())
s=[input() for _ in range(h)]

from collections import deque

sxy=[]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            sxy.append([i,j])
ddx=[1,-1,0,0]
ddy=[0,0,1,-1]

t=[[-1 for _ in range(w)] for _ in range(h)]
q=deque()
for txy in sxy:
    q.append(txy)
    t[txy[0]][txy[1]]=0

count=0
while q:
    y,x=q.popleft()
    count+=1
    for (dx,dy) in zip(ddx,ddy):
        ny=y+dy
        nx=x+dx
        if not (0<=nx<w and 0<=ny<h):continue
        if t[ny][nx]==-1:
            t[ny][nx]=t[y][x]+1
            q.append([ny,nx])
a=0
for i in range(h):
    for j in range(w):
        a=max(a,t[i][j])
print(a)
### BUGGY CODE ###

import bisect
from collections import defaultdict

S=input()
T=input()

def solve():
    obj=defaultdict(list)
    for i,s in enumerate(S):
        obj[s].append(i)

    result=1
    mx=-1
    for t in T:
        flag=True

        if not obj[t]:
            return -1

        
        pos=(obj[t]+[-1])[bisect.bisect_right(obj[t],mx)]
        if pos==-1:
            mx=obj[t][0]
            result+=1
        else:
            mx=pos

    if pos==-1:
        pos=obj[t][0]
    return len(S)*(result-1)+pos+1
print(solve())


### FIXED CODE ###

import bisect
from collections import defaultdict

S=input()
T=input()

def solve():
    obj=defaultdict(list)
    for i,s in enumerate(S):
        obj[s].append(i)

    result=1
    mx=-1
    for t in T:
        flag=True

        if not obj[t]:
            return -1

        
        bi_pos=bisect.bisect_right(obj[t],mx)
        if bi_pos==len(obj[t]):
            pos=-1
            mx=obj[t][0]
            result+=1
        else:
            pos=obj[t][bi_pos]
            mx=pos

    if pos==-1:
        pos=obj[t][0]
    return len(S)*(result-1)+pos+1
print(solve())
### BUGGY CODE ###

import  heapq

n,m,s,t=map(int,raw_input().split())
src = [ tuple( map( int, raw_input().split() ) )   for i in range(m)]

nl=[ [ ] for j in range(n+1) ] 

for u,v,a,b in src:
	nl[u].append( (v,a,b) )
	nl[v].append( (u,a,b) )

#Dijkstra yen
d_y=[ float("inf") ]*(n+1)
d_y[s]=0

Q=[]
heapq.heappush(Q,s)

while Q:
	u=heapq.heappop(Q)
	for i in nl[u]:
		v=i[0]
		yen=i[1]
		alt=d_y[u]+yen
		if d_y[v]> alt:
			d_y[v]=alt
			heapq.heappush(Q,v)

#Dijkstra snuuk
d_s=[ float("inf")]*(n+1)
d_s[t]=0

Q=[]
heapq.heappush(Q,t)

while Q:
	u=heapq.heappop(Q)
	for i in nl[u]:
		v=i[0]
		snuuku=i[2]
		alt=d_s[u]+snuuku
		if d_s[v]> alt:
			d_s[v]=alt
			heapq.heappush(Q,v)


val=float("inf")
A=[]
for i in range(n,0,-1):
	tmp=d_y[i]+d_s[i]
	val=min(val, tmp)
	A.append(val)

for i in reversed(A):
	print 10**15-i

### FIXED CODE ###

import heapq
 
N,M,S,T = map(int,input().split())
S,T = S-1,T-1
src = [tuple(map(int,input().split())) for i in range(M)]
 
es = [[] for i in range(N)]
for u,v,a,b in src:
    u,v = u-1,v-1
    es[u].append((v,a,b))
    es[v].append((u,a,b))
 
INF = float('inf')
cy = [INF] * N
cy[S] = 0
hq = [(0,S)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + a >= cy[to]: continue
        cy[to] = cost + a
        heapq.heappush(hq, (cy[to],to))
 
cs = [INF] * N
cs[T] = 0
hq = [(0,T)]
heapq.heapify(hq)
while hq:
    cost,v = heapq.heappop(hq)
    for to,a,b in es[v]:
        if cost + b >= cs[to]: continue
        cs[to] = cost + b
        heapq.heappush(hq, (cs[to],to))
 
ans = [INF]
for i in reversed(range(N)):
    tmp = cs[i] + cy[i]
    ans.append(min(ans[-1],tmp))
 
for a in reversed(ans[1:]):
    print(10**15 - a)
### BUGGY CODE ###

n=int(input())
s=[input()for i in range(n)]
cnt=0
for i in range(n):
    for j in range(i,n):
        if sorted(s[i])==sorted(s[j]):
            cnt+=1
print(cnt-n)

### FIXED CODE ###

import collections
n = int(input())
x = [''.join(sorted(input())) for _ in range(n)]
a = collections.Counter(x)
print(sum(i * ~-i // 2 for i in a.values()))
### BUGGY CODE ###

n = int(input())
f = 1
a = list(map(int, input().split()))
f = 1
for i in  a:
    f = f * i
if(f>1000000000000000000):
    print(-1)
else:
    print(f)


### FIXED CODE ###

def fun(a,n):
    if 0 in a:
        return 0
    z = 1
    for i in a:
        z=z*i 
        if(z>1000000000000000000):
            return -1
    return z

n = int(input())
a = list(map(int,input().split()))
f = fun(a,n)
print(f)
### BUGGY CODE ###

n,m=map(int,input().split())
l,r=map(int,input().split())
s={j for j in range(l,r+1)}
for i in range(1,m):
    l,r=map(int,input().split())
    s=s & {j for j in range(l,r+1)}
print(len(s))

### FIXED CODE ###

n,m=map(int,input().split())
l,r=map(int,input().split())
s=[l,r]
for i in range(1,m):
    l,r=map(int,input().split())
    if s[0]<l:
        s[0]=l
    if s[1]>r:
        s[1]=r

    if s[1]-s[0]<0:
        s=[0,-1]
        break
print(s[1]-s[0]+1)
### BUGGY CODE ###

MOD = int(1e9+7)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


def main():
    N = int(input())
    A = list(map(int, input().split()))
    M = 60
    bitcnt = [0] * M
    for a in A:
        for i in range(M):
            if a & (1 << i):
                bitcnt[i] += 1
    ans = 0
    for a in A:
        for i in range(M):
            if a & (1 << i):
                ans += (1 << i) * (N - bitcnt[i])
            else:
                ans += (1 << i) * bitcnt[i]
            ans %= MOD
    ans = div(ans, 2)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

MOD = int(1e9+7)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


def main():
    N = int(input())
    A = list(map(int, input().split()))
    M = 60
    bitcnt = [0] * M
    for a in A:
        for i in range(M):
            if a & (1 << i):
                bitcnt[i] += 1
    ans = 0
    for a in A:
        for i in range(M):
            x = 1 << i
            if a & x:
                ans = (ans + x * (N - bitcnt[i])) % MOD
            else:
                ans = (ans + x * bitcnt[i]) % MOD
    ans = div(ans, 2)
    print(ans)


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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N,T = map(int,readline().split())
m = map(int,read().split())
ls = sorted(zip(m,m))

deli = [0]*N
deli[- 1] = ls[-1][- 1]
for i in range(N - 2, 0, - 1):
    deli[i] = max(deli[i + 1], ls[i][- 1])

res = 0
dp = [0]*T
for i in range(N - 1):
    for j in range(T - 1, - 1, - 1):
        if ls[i][0] <= j:
            dp[j] = max(dp[j], dp[j - ls[i][0]] + ls[i][1])
    res = max(res, dp[- 1] + deli[i + 1])
print(res)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, T = map(int, readline().split())

AB= list(map(int, read().split()))
A = AB[0::2]
B = AB[1::2]
ls = list(zip(A, B))
# 食べるのにかかる時間で昇順にソート
ls.sort()
# 上の並び順において、ls[i:]の美味しさの最大値をdeli[i]とする
deli = [0]*N
deli[- 1] = ls[-1][- 1]
for i in range(N - 2, - 1, - 1):
    deli[i] = max(deli[i - 1], ls[i][- 1])

res = 0
dp = [0]*T
for i in range(N - 1):
    for j in range(T - 1, - 1, - 1):
        if ls[i][0] <= j:
            dp[j] = max(dp[j], dp[j - ls[i][0]] + ls[i][1])
    res = max(res, dp[- 1] + deli[i + 1])
print(res)
### BUGGY CODE ###

from collections import deque
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    H, W = map(int, input().rstrip().split())
    G = []
    for i in range(H):
        s = list(input())
        G.append(s)
    # print(G)

    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    INF = 10 ** 18 + 10

    def bfs(i, j):
        d = [[INF for k in range(W)] for l in range(H)]
        q = deque()
        q.append((i, j))
        d[i][j] = 0
        cnt = 1
        while q:
            a, b = q.popleft()
            for k in range(4):
                to_w = max(0, min(W - 1, b + dx[k]))
                to_h = max(0, min(H - 1, a + dy[k]))
                if G[to_h][to_w] == "#":
                    continue
                if d[to_h][to_w] != INF:
                    continue
                if to_w != j and to_h != i:
                    continue
                d[to_h][to_w] = d[a][b] + 1
                q.append((to_h, to_w))
                cnt += 1
        # print(i, j, cnt)
        return cnt

    res = 0
    for h in range(H):
        for w in range(W):
            if G[h][w] == "#":
                continue
            res = max(res, bfs(h, w))
    # bfs(2, 5)
    print(res)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    H, W = map(int, input().rstrip().split())
    G = []
    for i in range(H):
        s = list(input())
        G.append(s)
    # print(G)
    cnt = [[0 for j in range(W)] for i in range(H)]

    for i in range(H):
        done = [0] * W
        for j in range(W):
            if G[i][j] == "#":
                continue
            if done[j]:
                continue
            length = 0
            while j + length < W:
                if G[i][j+length] == "#":
                    break
                length += 1
            for k in range(length):
                cnt[i][j + k] += length
                done[j + k] = 1

    for j in range(W):
        done = [0] * H
        for i in range(H):
            if G[i][j] == "#":
                continue
            if done[i]:
                continue
            length = 0
            while i + length < H:
                if G[i+length][j] == "#":
                    break
                length += 1
            for k in range(length):
                cnt[i + k][j] += length
                done[i + k] = 1
    ans = 0
    for i in range(H):
        ans = max(ans, max(cnt[i]) - 1)
    print(ans)


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

from collections import deque

def main():
    n, m = list(map(int, input().split(" ")))
    v_set = [set([]) for _ in range(n)]
    for _ in range(m):
        a, b = list(map(int, input().split(" ")))
        v_set[a-1].add(b-1)
        v_set[b-1].add(a-1)

    max_num = 0
    checked_list = []
    seen = [0]*n
    for ni in range(n):
        if seen[ni]:
            continue
        checked = []
        stack = deque([ni])
        while stack:
            cur = stack.pop()
            seen[cur]+=1
            checked.append(cur)
            for next_i in v_set[cur]:
                if seen[next_i] or next_i in stack:
                    continue
                stack.append(next_i)
        max_num = max(max_num, len(checked))
        checked_list.append(checked)

    print(max_num)

if __name__=="__main__":
    main()


### FIXED CODE ###

from collections import deque

def main():
    n, m = list(map(int, input().split(" ")))
    v_set = [set([]) for _ in range(n)]
    for _ in range(m):
        a, b = list(map(int, input().split(" ")))
        v_set[a-1].add(b-1)
        v_set[b-1].add(a-1)

    max_num = 0
    checked = [0]*n
    for ni in range(n):
        if checked[ni]:
            continue
        stack = deque([ni])
        checked[ni] = 1
        f = 1
        while stack:
            cur = stack.pop()
            for next_i in v_set[cur]:
                if checked[next_i]:
                    continue
                stack.append(next_i)
                checked[next_i] = 1
                f+=1
        max_num = max(max_num, f)

    print(max_num)

if __name__=="__main__":
    main()