Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python3
from unionfind import unionfind
N, M = map(int, input().split())
u = unionfind(N + M)
for i in range(N):
    L = [int(x) - 1 for x in input().split()]
    L[0] += 1
    for j in range(L[0]):
        u.unite(L[j + 1], M + i)

ans = True
for i in range(N):
    if not u.issame(M, M + i):
        ans = False
print(('NO', 'YES')[ans])


### FIXED CODE ###

#!/usr/bin/env python3
class UnionFind():
    def __init__(self, size):
        self.table = [-1] * size

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s2] < self.table[s1]: s1, s2 = s2, s1
            self.table[s1] += self.table[s2]
            self.table[s2] = s1
        return s1 != s2


N, M = map(int, input().split())
uf = UnionFind(N + M)
for i in range(N):
    L = [int(x) - 1 for x in input().split()]
    L[0] += 1
    for j in range(L[0]):
        uf.union(L[j + 1], M + i)

ans = True
for i in range(N):
    if uf.find(M + i) != uf.find(M):
        ans = False
print(('NO', 'YES')[ans])
N,M = input().split()
N,M = int(N),int(M)
a = [0 for i in range(M)]
b = [[] for i in range(M)]

for k in range(M):
    a[k],b_ = input().split()
    a[k],b_ = int(a[k]),int(b_)
    
    b[k] = input().split()
    b[k] = [int(j)-1 for j in b[k]] 
#print(b)
def box(i,bo):#i :i番目の鍵 b空いている宝箱
    #if(0 not in bo):
        #i=M
        #return 0
    #elif(i==M and 0 in bo):
        #return 1e+20
    
    if(i==M):
        if(0 in bo):
            return 1e+20
        else:
            return 0
    else:
        if(0 not in bo):
            return 0
    
        else:
        
            p1 = box(i+1,bo)

            new_bo = bo.copy()
            for k in range(len(b[i])):
                new_bo[b[i][k]] += 1

            p2 = box(i+1,new_bo)+a[i]
            return min([p1,p2])
        
box_ = [0 for i in range(N)]
num = box(0,box_)
if(num>=1e+20):
    print(-1)
else:
    print(num)
    
#宝箱はN(<=12)個

### FIXED CODE ###

N = int(input())
if(N%2==0):
    print(0.5)
else:
    print((0.5*(N+1))/N)
N=int(input())
road_list = [[] for i in range(N)]

for i in range(N-1):
    a,b=list(map(int,input().split()))
    a=a-1
    b=b-1
    road_list[a].append(b)
    road_list[b].append(a)
c = list(map(int,input().split()))
from collections import deque
Q = deque([[0,0]])
ans = []
checked_list = [False for i in range(N)]
checked_list[0]=True
count_list = [10**9 for i in range(N)]
count_list[0] = 0

while len(Q)>0:
    v,count = Q.pop()
    count+=1
    for v1 in road_list[v]:        
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.append([v1,count])
            count_list[v1]=count

c.sort()

count_list = [[i,count_list[i]] for i in range(N)]
count_list = sorted(count_list, key=lambda x:x[1],reverse=True)
d = [[count_list[i][0],c[i]] for i in range(N)]
d = sorted(d, key=lambda x:x[0])
d = [d[i][1] for i in range(N)]
print(sum(c[:-1]))
print(*d)


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

### FIXED CODE ###


N=int(input())
road_list = [[] for i in range(N)]

for i in range(N-1):
    a,b=list(map(int,input().split()))
    a=a-1
    b=b-1
    road_list[a].append(b)
    road_list[b].append(a)
c = list(map(int,input().split()))
from collections import deque
Q = deque([[0,0]])
ans = []
checked_list = [False for i in range(N)]
checked_list[0]=True
count_list = [10**9 for i in range(N)]
count_list[0] = 0

while len(Q)>0:
    v,count = Q.pop()
    count+=1
    for v1 in road_list[v]:        
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.append([v1,count])
            count_list[v1]=count

c.sort()

count_list = [[i,count_list[i]] for i in range(N)]
count_list = sorted(count_list, key=lambda x:x[1],reverse=True)
d = [[count_list[i][0],c[i]] for i in range(N)]
d = sorted(d, key=lambda x:x[0])
d = [d[i][1] for i in range(N)]
print(sum(c[:-1]))
print(*d)
#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
  
n,m=input2()
AB=[input_array() for _ in range(m)]


uf = UnionFind(n)
for ab in AB:
	a=ab[0]
	b=ab[1]
	uf.union(a-1,b-1)

ans=0
for i in uf.parents:
	if i < 0:
		ans+=1
print(ans-1)

### FIXED CODE ###

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

class UnionFind():
	"""docstring for UnionFind"""
	def __init__(self, n):
		self.parents = [-1]*n

	def find(self,x):
		if self.parents[x] < 0: #自分が親である時
			return x
		else: #自分が子供である時
			self.parents[x]=self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		# 各要素の親要素を返す
		x=self.find(x)
		y=self.find(y)

		if x==y:
			return
		if self.parents[x] > self.parents[y]:
			x,y=y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x
		# print(self.parents)
n,m=input2()
AB=[input_array() for _ in range(m)]


uf = UnionFind(n)
for ab in AB:
	a=ab[0]
	b=ab[1]
	uf.union(a-1,b-1)

ans=0
for i in uf.parents:
	if i < 0:
		ans+=1
print(ans-1)
import math

def sum_of_digits(n):
    s = 0
    l = len(str(n))
    for i in range(l):
        s += n%10
        n = int(n/10)
    return s

def main():
    s = int(input())
    s = sum_of_digits(s)
    if s != 0 and s % 9==0:
        print('Yes')
    else:
        print('No')

if __name__=="__main__":
  main()

### FIXED CODE ###

import math

def main():
    s = sum(list(map(int, input())))
    if s % 9==0:
        print('Yes')
    else:
        print('No')

if __name__=="__main__":
  main()
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

N, C = map(int,input().split())
Mx = 10**5+1
sch = [0]*Mx
plist = [[] for _ in range(C)]
for _ in range(N):
    s, t, c = map(int,input().split())
    plist[c-1].append((s,t))
for p in plist:
    p.sort()
    prevt = 0
    for s, t in p:
        sch[s] += 1
        sch[t+1] -= 1
        if prevt == s:
            sch[prevt+1] += 1
            sch[s] -= 1
        prevt = t
for i in range(1,Mx):
    sch[i]+=sch[i-1]
print(max(sch))


### FIXED CODE ###

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

from collections import deque

N, C = map(int,input().split())
Mx = 10**5+1
sch = [[0]*Mx for _ in range(C)]
scht = [0]*Mx
plist = [[] for _ in range(C)]
for _ in range(N):
    s, t, c = map(int,input().split())
    plist[c-1].append((s,t))
for c, p in enumerate(plist):
    p.sort()
    prevt = 0
    for s, t in p:
        if prevt == s:
            sch[c][prevt] = 0
        else:
            sch[c][s] = 1
        sch[c][t] = -1
        prevt = t
    for i in range(1, Mx):
        if sch[c][i]==1:
            scht[i-1]+=1
        if sch[c][i]==-1:
            scht[i]-=1

for i in range(1, Mx):
    scht[i] += scht[i-1]

print(max(scht))
H, W = (int(i) for i in input().split())
e = [input() for i in range(H)] 

new_e = []
for row in e:
    if row.count("#") > 0:
        new_e.append(row)

not_use_col = list(range(W))
use_col = []
for row in new_e:
    for col in not_use_col:
        if row[col] == "#":
            use_col.append(not_use_col.pop(col))
            break

for row in new_e:
    x=""
    for col in use_col:
        x += row[col]
    print(x)



### FIXED CODE ###

H, W = (int(i) for i in input().split())
e = [input() for i in range(H)] 

new_e = []
for row in e:
    if row.count("#") > 0:
        new_e.append(row)

use_col = []
for row in new_e:
    for col in range(W):
        if row[col] == "#" and col not in use_col:
            use_col.append(col)
            
for row in new_e:
    x=""
    for col in sorted(use_col):
        x += row[col]
    print(x)
n=int(input())
*a,=map(int,input().split())
t_ans =0
for i in range(n):
	t_ans  += 1/a[i]
ans = 1/t_ans
print(ans)

### FIXED CODE ###

a,b=map(int,input().split())
plg=1
cnt =0
while True:
	if plg < b:
		plg += a-1
		cnt += 1
	else:
		break
print(cnt)
import sys

x = int(sys.argv[1])                                                                                             
 print(x * x * x)

### FIXED CODE ###

x = int(input())
print(x * x * x)
hit = blow = 0
a = [*map(int,input().split(' '))]
b = [*map(int,input().split(' '))]
for i in range(4):
	if a[i] == b[i]:
		hit += 1
		elif a[i] == b[i-1]:
			blow += 1
print(hit, blow)


### FIXED CODE ###

while 1:
	hit = blow = 0
	try: a = list(map(int,input().split()))
	except: break
	b = list(map(int,input().split()))
	for i in range(4):
		if a[i] == b[i]:
			hit += 1
		elif a[i] in b:
			blow += 1
	print(hit, blow)
import sys
sys.setrecursionlimit(10*10)
def MI(): return map(int, input().split())
from collections import deque
N,Q=MI()
Edge=[[] for _ in range(N)]
for i in range(N-1):
  a,b=MI()
  Edge[a-1].append(b-1)
  Edge[b-1].append(a-1)
Point=[0]*N
for i in range(Q):
  p,x=MI()
  Point[p-1]+=x
def dfs(now,pre=-1):
  for nxt in Edge[now]:
    if nxt==pre:
      continue
    Point[nxt]+=Point[now]
    dfs(nxt,now)
dfs(0)
print(*Point)


### FIXED CODE ###

#ika tako
import sys
n, q = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
for line in lines[:n - 1]:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
adds = [0] * n
for line in lines[n - 1:]:
    p, x = map(int, line.split())
    p -= 1
    adds[p] += x
ans = [-1] * n
q = [(0, 0)]
while q:
    v, a = q.pop()
    a += adds[v]
    ans[v] = a
    for u in links[v]:
        if ans[u] == -1:
            q.append((u, a))
print(*ans)
n=int(input())
d_s=input().split()
d_i=[int(x) for x in d_s]
d=sorted(d_i)
k=d[n/2]
t=d[n/2-1]
print(k-t)

### FIXED CODE ###

n=int(input())
d_s=input().split()
d_i=[int(x) for x in d_s]
d=sorted(d_i)
k=d[int(n/2)]
t=d[int(n/2)-1]
print(k-t)
n, m = list(map(int, input().split()))
def cutterl(l, lst) :
    if lst == [] :
        return []
    elif lst[0] < l :
        return cutterl(l, lst[1:])
    else :
        return lst
def cutterr(r, lst) :
    if lst == [] :
        return []
    elif r < lst[-1] :
        return cutterr(r, lst[:-1])
    else :
        return lst
nlist = list(map(lambda x : x + 1, range(n)))
for i in range(m) :
    l, r = list(map(int, input().split()))
    nlist = cutterl(l, nlist)
    nlist = cutterr(r, nlist)
print(len(nlist))

### FIXED CODE ###

n, m = list(map(int, input().split()))
llist = []
rlist = []
for i in range(m) :
    l, r = list(map(int, input().split()))
    llist.append(l)
    rlist.append(r)
ll = max(llist)
rr = min(rlist)
print(max(0, min(rr, n)-ll+1))
import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if sum(ANS[a[1]:a[1]+L]) < (a[0]-1)*(L-1) + MAX + 1
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == MAX:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
parameter = 0.995
MAX = 10**9+1
ANS = [MAX]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
n,m=map(int,input().split())
wa=0
hoge=[0 for i in range(n)]
huga=[0 for i in range(n)]
for i in range(m):
  a,b=map(str,input().split())
  if(hoge[int(a)-1]==0 and b=="AC"):
    hoge[int(a)-1]=1
  if(hoge[int(a)-1]==0 and b=="WA"):
    huga[int(a)-1]=1
    
for i in range(n):
  if(hoge[i]==0):
    huga=0
    
print(sum(hoge),sum(huga))

### FIXED CODE ###

n,m=map(int,input().split())
hoge=[0 for i in range(n)]
huga=[0 for i in range(n)]
for i in range(m):
  a,b=map(str,input().split())
  if(hoge[int(a)-1]==0 and b=="AC"):
    hoge[int(a)-1]=1
  if(hoge[int(a)-1]==0 and b=="WA"):
    huga[int(a)-1]+=1
    
for i in range(n):
  if(hoge[i]==0):
    huga[i]=0
    
print(sum(hoge),sum(huga))
n=int(input)

a=list()
for i in range(n):

    a.append(list(map(int,input().strip().split())))
a=list(set(a))
ans=0
for i in range(len(a)):
    for j in range(i+1,len(a)):
        ans=max(ans,abs(a[i][0]-a[j][0])+abs(a[j][1],a[i][1]))

print(ans)

### FIXED CODE ###

s=int(input())
a=[0]*2001
x=(10**9)+7
if s<3:
    print(0)
    exit()

    
else:

    for i in range(3,6):
        a[i]=1

    for i in range(6,2001):
        a[i]=(sum(a[3:i-2])+1)%(x)

print(a[s])
N,P =map(int,input().split(' '))
if N==1:
    print(P)
    exit()
for i in range((pow(P,1/N))//1,0,-1):
    if P%pow(i,N)==0:
        print(i)
        break

### FIXED CODE ###

from collections import Counter
N,P =map(int,input().split(' '))
if N==1:
    print(P)
    exit()
prime = []
f = 2
while f**2 <=P:
    if P%f==0:
        prime.append(f)
        P//=f
    else:
        f += 1
if P != 1:
    prime.append(f)

ans = 1
for k,v in Counter(prime).items():
    if v//N:
        ans *= k**(v//N)
print(ans)
from sys import stdin

n = int(stdin.readline().rstrip())
d = [int(x) for x in stdin.readline().rstrip().split()]

m = [0] * 100

for i in d:
    m[i] += 1

result = 0
for i in m:
    if (i > 1):
        result += 1

if (result > 0):
    print("No")
else:
    print("Yes")

### FIXED CODE ###

from sys import stdin
import math

n = int(stdin.readline().rstrip())
a = [int(x) for x in stdin.readline().rstrip().split()]

d = {}
for aa in a:
    if aa in d.keys():
        d[aa] += 1
    else:
        d[aa] = 1

result = 'YES'
for key, value in d.items():
    if value > 1:
        result = 'NO'

print(result)
N = input()
A = input()
FLG = 0
for i in range(A):
  if (N-i)%500 == 0:
    print('YES')
    FLG = 1
	break
if FLG == 0:
  print('NO')


### FIXED CODE ###

N = int(input())
A = int(input())
if (N%500) > A:
  print('No')
else:
  print('Yes')
from math import ceil
D,G=map(int,input().split())
p=[0]*D
c=[0]*D

for i in range(D):
    p[i],c[i]=map(int,input().split())
_min=101*D

flag=1
while(flag < 2**D):
    
    _G=G
    tmp=0
    max_ind=0
    for i in range(D):
        if(flag & 1<<i):
            _G-=p[i]*(i+1)*100 + c[i]
            tmp+=p[i]
        else:
            max_ind=i
    k=ceil(max([(_G),0])//(100*(max_ind+1)))  
    if(k < p[max_ind]):
        tmp+=k
        _min=min([tmp,_min])
    flag+=1
print(_min) 

### FIXED CODE ###

n=int(input())
if(n<=1199):
    print("ABC")
elif(n<2800):
    print("ARC")
else:
    print("AGC")
MOD = 10**9+7
memo = {}
def steps(n):
  if not(n in memo):
    if n == 0:
      memo[n] = 1
    elif n == 1:
      memo[n] = 1
    else:
      memo[n] = (steps(n-1)+steps(n-2))%MOD
  return memo[n]

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
nowstep = 0
ans = 1
for a in A:
  if nowstep == a:
    ans = 0
    break
  ans = (ans * steps(a-1-nowstep))%MOD
  nowstep = a+1
ans = (ans * steps(N-nowstep))%MOD
print(ans)



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

MOD = 10**9+7
memo = {}
def steps(n):
  if not(n in memo):
    if n == 0:
      memo[n] = 1
    elif n == 1:
      memo[n] = 1
    else:
      memo[n] = (steps(n-1)+steps(n-2))%MOD
  return memo[n]

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
nowstep = 0
ans = 1
for a in A:
  if nowstep == a:
    ans = 0
    break
  ans = (ans * steps(a-1-nowstep))%MOD
  nowstep = a+1
ans = (ans * steps(N-nowstep))%MOD
print(ans)
s,t=open(0)
print(min(sum(a!=b for a,b in zip(s[i:],t[:-1]))for i in range(len(s)-len(t))))

### FIXED CODE ###

s = input()
t = input()
ans = len(t)
for i in range(len(s) - len(t) + 1):
    ans = min(ans, sum(si != ti for si, ti in zip(s[i:], t)))
print(ans)
def com(n):
    return n*(n-1)//2
ans=0
n=int(input())
a=list(map(int,input().split()))
coun=[0]*n
for i in range(n):
    coun[a[i]]+=1
foi i in range(n):
    ans+=com(coun[i])
for i in range(n):
    m=com(coun[a[i]]-1)
    o=com(coun[a[i]])
    print(ans-o+m)
 

### FIXED CODE ###

import collections
N=int(input())
lst=input().split()
s=0
dic=collections.Counter(lst)
for i in dic.values():
    s+=(i*i-i)//2
for i in lst:
    print(s+1-dic[i])
import sys
input = sys.stdin.readline
N = int(input())
a = tuple(map(int, input().split()))
b = tuple(map(int, input().split()))
dp = [0] * (N + 1)
res = 0
for i in range(N, -1, -1):
  for j in range(3):
    if a[j] < b[j] and (i - a[j] >= 0): dp[i - a[j]] = max(dp[i - a[j]], dp[i] + b[j])
  res = max(res, i + dp[i])
#print(res)
d = []
for i in range(3):
  if a[i] > b[i]: d.append((b[i], a[i]))
if len(d) == 0: print(res)
elif len(d) == 1:
  res = res // d[0][0] * d[0][1] + res % d[0][0]
  print(res)
elif len(d) == 2:
  dp = [0] * (res + 1)
  rres = 0
  for i in range(res, -1, -1):
    for x, y in d:
      if i - x >= 0: dp[i - x] = max(dp[i - y], dp[i] + y)
    rres = max(rres, i + dp[i])
  print(rres)
else:
  dp = [0] * (res + 1)
  for i in range(res, -1, -1):
    for j in range(3):
      if a[j] > b[j] and (i - b[j] >= 0): dp[i - b[j]] = max(dp[i - b[j]], dp[i] + a[j])
    res = max(res, i + dp[i])
  print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
d1 = []
d2 = []
for i in range(3):
  if a[i] < b[i]: d1.append((a[i], b[i]))
  if a[i] > b[i]: d2.append((b[i], a[i]))

dp = [0] * (N + 1)

for i in range(N, -1, -1):
  for t in d1:
    x = t[0]
    y = t[1]
    if i - x >= 0:
      dp[i - x] = max(dp[i - x], y + dp[i])
for i in range(N + 1): dp[i] += i

def calc(x, r1):
  z = r1 - d2[0][0] * x
  return (z // d2[1][0]) * d2[1][1] + z % d2[1][0] + d2[0][1] * x

res1 = max(dp)
if len(d2) == 0:
  print(res1)
if len(d2) == 1:
  x, y = d2.pop()
  print((res1 // x) * y + (res1 % x))
if len(d2) == 2:
  x0 = 0
  x3 = res1 // d2[0][0]
  res2 = res1 + 0
  for x in range(x0, x3 + 1):
    res2 = max(res2, calc(x, res1))
  print(res2)

if len(d2) == 3:
  dp2 = [0] * (res1 + 1)
  for i in range(res1, -1, -1):
    for t in d2:
      x = t[0]
      y = t[1]
      if i - x >= 0:
        dp2[i - x] = max(dp2[i - x], y + dp2[i])
  for i in range(res1 + 1): dp2[i] += i
  print(max(dp2))
s = input()

while(True):
  for i in ['dream', 'dreamer', 'erase', 'eraser']:
    if s.endwith(i):
      s = s[:-len(i)]
      break
  else:
    print('NO')
    break
  
  if not s:
    print('YES')
    break

### FIXED CODE ###

n = int(input())
s = [0, 0, 0]
ans = 'Yes'
for i in range(n):
  l = list(map(int, input().split()))
  diff_t = l[0] - s[0]
  diff_x = abs(s[1] - l[1])
  diff_y = abs(s[2] - l[2])
  s = [l[0], l[1], l[2]]
  if diff_x + diff_y > diff_t or (diff_t - diff_x - diff_y) % 2 != 0:
    ans = 'No'
print(ans)
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
moves = [[0,1], [0,-1],[1,0], [-1,0]]

def bfs(b, a):
  light = [[0 for _ in range(w)] for _ in range(h)]
  q = deque([(b, a, (0, 1, 2, 3))])
  ans = 0
  while q:
    y, x, direction= q.popleft()
    light[y][x] = 1
    ans += 1
    
    for i in direction:
      next_y = y + moves[i][0]
      next_x = x + moves[i][1]
      if 0 <= next_y < h and 0 <= next_x < w and s[next_y][next_x] == '.' and light[next_y][next_x] == 0:
        q.append([next_y, next_x, [i]])
  return ans
bfs(2, 5)
final_ans = 0
for i in range(h):
  for j in range(w):
    final_ans = max(final_ans, bfs(i, j))

print(final_ans)



### FIXED CODE ###

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

L = [[0 for _ in range(w)] for _ in range(h)]
R = [[0 for _ in range(w)] for _ in range(h)]
D = [[0 for _ in range(w)] for _ in range(h)]
U = [[0 for _ in range(w)] for _ in range(h)]

for i in range(h):
  for j in range(w):
    if s[i][j] == '.':
      if j == 0:
        L[i][j] = 1
      else:
        L[i][j] = L[i][j-1]+1     
      if i == 0:
        D[i][j] = 1
      else:
        D[i][j] = D[i-1][j]+1
      if i == h-1:
        U[i][j] = 1
      else:
        U[i][j] = U[i+1][j]+1
  for j in range(w-1, -1, -1):
    if s[i][j] == '.':
      if j == w-1:
        R[i][j] = 1
      else:
        R[i][j] = R[i][j+1]+1

for i in range(h-1, -1, -1):
  for j in range(w):
    if s[i][j] == '.':
      if i == h-1:
        U[i][j] = 1
      else:
        U[i][j] = U[i+1][j]+1
ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans, L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)

print(ans)
# coding: utf-8

A, B = [int(i) for i in input().split()]

def count_1(bi, idx):
    bi = bi[::-1]
    cnt = 0
    if idx > 0:
        for i in range(0, idx):
            cnt += int(bi[idx]) * int(bi[i]) * int(2**i)
    if idx < (len(bi) - 1):
        for i in range(idx + 1, len(bi)):
            cnt += int(bi[i]) * int(2**i) / 2
    cnt += int(bi[idx])        
    return(int(cnt))

a = str(bin(A-1))[2:]
b = str(bin(B))[2:]
a = (len(b) - len(a)) * "0" + a # 長さ調整

def count_1s(bi):
    return([count_1(bi, i) for i in range(len(bi))[::-1]])

a_cnt = count_1s(a)
b_cnt = count_1s(b)

print(int("".join([str((i - j) % 2) for i, j in zip(b_cnt, a_cnt)]), 2))


### FIXED CODE ###

# coding: utf-8

A, B = [int(i) for i in input().split()]

def count_1(bi, idx):
    bi = bi[::-1]
    cnt = 0
    if idx > 0:
        for i in range(0, idx):
            cnt += int(bi[idx]) * int(bi[i]) * int(2**i)
    if idx < (len(bi) - 1):
        for i in range(idx + 1, len(bi)):
            cnt += int(bi[i]) * int(2**i) / 2
    cnt += int(bi[idx])        
    return(int(cnt))

a = str(bin(max(A-1, 0)))[2:]
b = str(bin(B))[2:]
a = (len(b) - len(a)) * "0" + a # 長さ調整

def count_1s(bi):
    return([count_1(bi, i) for i in range(len(bi))[::-1]])

a_cnt = count_1s(a)
b_cnt = count_1s(b)


print(int("".join([str((i - j) % 2) for i, j in zip(b_cnt, a_cnt)]), 2))
n = int(input())
s = [input() for i in range(n)]
m = int(input())
t = [input() for i in range(m)]
ans=len(s)

for i in range(n):
  for j in range(m):
    if s[i] == s[j]:
      ans-=1
if ans < 0:
  print("0")
else:
  print(ans)

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
m = int(input())
t = [input() for i in range(m)]
ans = 0
for i in range(n):
  tmp=0
  for j in range(n):
    if s[i] == s[j]:
      tmp+=1
  for j in range(m):
    if s[i] == t[j]:
      tmp-=1
  ans=max(ans,tmp)
print(ans)
import math
import numpy as np

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

def check():
    x = np.arange(1, N+1)
    tmp = np.floor((A * x)/B ) - (A * np.floor(x / B))
    #ans = math.floor((A * x)/B) - (A*math.floor(x/b))
    print(int(max(tmp)))


def solve():
    ans = 0
    for x in range(1, N+1):
        tmpans = math.floor((A * x)/B) - (A * math.floor(x/B))
        ans = max(tmpans, ans)
    print(ans)
#solve()
check()


### FIXED CODE ###

import math

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

if N < B:
    x = N
else:
    x = B - 1

def check(x):
    return math.floor((A * x) / B)
            
print(check(x))