Harryxun/stf_run huggingface dataset:
import sys
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, csgraph_from_dense

input = sys.stdin.readline


def main():
    N = int(input())
    edge = [[0] * N for j in range(N)]
    for _ in range(N - 1):
        a, b, c = [int(x) for x in input().split()]
        edge[a - 1][b - 1] = c
        edge[b - 1][a - 1] = c

    G = csgraph_from_dense(edge, null_value=0)
    d = shortest_path(G)

    Q, K = [int(x) for x in input().split()]
    for _ in range(Q):
        x, y = [int(x) for x in input().split()]
        print(int(d[x - 1][K - 1] + d[K - 1][y - 1]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline

d = []
ABC = []

sys.setrecursionlimit(10 ** 8)


def solve(i, dis):
    global d
    global ABC
    d[i] = dis

    for n, c in ABC[i]:
        if d[n] == -1:
            solve(n, dis + c)


def main():
    N = int(input())
    global ABC
    ABC = [[] for _ in range(N + 1)]
    global d
    d = [-1] * (N + 2)
    for _ in range(N - 1):
        a, b, c = [int(x) for x in input().split()]
        ABC[a - 1].append([b - 1, c])
        ABC[b - 1].append([a - 1, c])

    Q, K = [int(x) for x in input().split()]

    solve(K - 1, 0)

    for _ in range(Q):
        x, y = [int(x) for x in input().split()]
        print(d[x - 1] + d[y - 1])


if __name__ == '__main__':
    main()
n, d = map(int, input().split())
s = 0
for i in range(n+1):
	x, y = map(int, input().split())
	if x**2+y**2 <= d**2:
		s = s+1
print(s)

### FIXED CODE ###

n, d = map(int, input().split())
s = 0
for i in range(n):
	x, y = map(int, input().split())
	if x**2+y**2 <= d**2:
		s += 1
print(s)
def resolve():
    from scipy.sparse.csgraph import shortest_path
    from scipy.sparse import csr_matrix
    import numpy as np
    n, m = map(int, input().split())
    edge = np.array([input().split() for _ in range(m)], dtype=np.int64).T
    a = csr_matrix(([1] * m, (edge - 1)), shape=(n, n)).toarray()
    s, p = shortest_path(a, return_predecessors=True,
                         indices=0, directed=False)  # 最短経路p
    if min(s[1:]) < 1:
        print("No")
    else:
        print("Yes")
        for i in p[1:]:
            print(i + 1)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

def resolve():
    def Dijkstra(s, n, edge, inf=float("inf")):
        import heapq
        d = [inf] * n
        used = [False] * n
        d[s] = 0
        used[s] = True
        queue = []
        path = [-9999] * n
        for e in edge[s]:
            heapq.heappush(queue, e + [s])
        while len(queue):
            dist, point, before = heapq.heappop(queue)
            if used[point]:
                continue
            d[point] = dist
            used[point] = True
            path[point] = before
            for nextdist, nextp in edge[point]:
                if not used[nextp]:
                    heapq.heappush(queue, [dist + nextdist, nextp, point])
        return d, path
    n, m = map(int, input().split())
    inf = 10 ** 10
    edge = [[] for _ in range(n)]
    for _ in range(m):
        x, y = [int(x) - 1 for x in input().split()]
        edge[x].append([1, y])
        edge[y].append([1, x])
    l, p = Dijkstra(0, n, edge, inf)
    if min(p[1:]) < -1:
        print("No")
    else:
        print("Yes")
        for i in p[1:]:
            print(i + 1)


if __name__ == '__main__':
    resolve()
a, b, c = map(raw_input().split())

if a < b < c:
  print 'Yes'
else:
  print 'No'

### FIXED CODE ###

a, b, c = map(int, raw_input().split())

if a < b and b < c:
  print 'Yes'
else:
  print 'No'
w = {'Sunny':'Cloud', 'Cloud':'Rainy', 'Rainy':'Sunny'}
print(w[input()])

### FIXED CODE ###

w = {'Sunny':'Cloudy', 'Cloudy':'Rainy', 'Rainy':'Sunny'}
print(w[input()])
#045c
S = list(input())

#allは2**9=512なので全探索でOK

ans = 0

for i in range(0,2**(len(S)-1)):
    bit = str(bin(i))[2:].zfill(len(S)-1)
    #print(bit,":",end="") 
    number = int(S[0])
    
    for j in range(len(bit)):

        if bit[j] == "0":
            number = number*10 + int(S[j+1])
        else:
            #print("+",number,end="")
            ans += number
            number = int(S[j+1])
            
    #print("+",number)
    ans += number
    
print(ans)

### FIXED CODE ###

#045c
S = list(input())

#allは2**9=512なので全探索でOK
if len(S)==1:
  print(int(S[0]))
else:
  ans = 0

  for i in range(0,2**(len(S)-1)):
      bit = str(bin(i))[2:].zfill(len(S)-1)
      #print(bit,":",end="") 
      number = int(S[0])

      for j in range(len(bit)):

          if bit[j] == "0":
              number = number*10 + int(S[j+1])
          else:
              #print("+",number,end="")
              ans += number
              number = int(S[j+1])

      #print("+",number)
      ans += number

  print(ans)
#input
N = int(input())
Tree = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    Tree[a].append(b)
    Tree[b].append(a)

# process
# 距離3の頂点を抽出
pair = []
for i in range(N):
    for j in Tree[i]:
        for k in Tree[j]:
            if k == i:
                continue
            for l in Tree[k]:
                if l == j or i > l:
                    continue
                pair.append((i,l))

# 順列を求める
def getAddNum(x, ans):
    t = 0
    for i in range(N):
        if (x+i)%3 == 0:
            t = i

    l = [x for x in range(t, N, 3)]
    for y in l:
        if not y in ans:
            return y

    return -1

def getMulNum(x, ans):
    l = []
    if x%3 == 0:
        return 0
    else:
        l = [n*3 for n in range(1, N//3+1)]

        for y in l:
            if not y in ans:
                return y

    return -1

def getNextNum(x, ans):
    for y in range(x+1, N+1):
        if not y in ans:
            return y
    
ans = [-1 for _ in range(1, N+1)]
n = 0
for a, b in pair:
    a -= 1
    b -= 1
    if ans[a] == -1:
        ans[a] = getNextNum(n, ans)
    
    t = getAddNum(ans[a], ans)
    if t > 0:
        ans[b] = t
    else:
        t = getMulNum(ans[a], ans)
        if t == 0:
            continue
        elif t > 0:
            ans[b] = t
        else:
            ans = []
            break

for i in range(N):
    if ans[i] == -1:
        ans[i] = getNextNum(n, ans)

# output
# print(pair)
if len(ans) == 0:
    print(-1)
else:
    print(" ".join(map(str, ans)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
from collections import deque

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

# process
# 頂点を2グループに分類
group = [-1]*N
group[0] = False
def categorize2g(pi, i, g):
    for ci in Edges[i]:
        if ci == pi:
            continue
        group[ci] = not g
        categorize2g(i, ci, not g)

categorize2g(-1, 0, 0)

# 順列を求める
ans = [0]*N
mod0 = [x for x in range(1, N+1) if x%3 == 0]
mod1 = [x for x in range(1, N+1) if x%3 == 1]
mod2 = [x for x in range(1, N+1) if x%3 == 2]
gtnum = sum(group)
if gtnum <= N//3:
    dq = deque(mod1+mod2+mod0)
elif N-gtnum <= N//3:
    dq = deque(mod0+mod1+mod2)
else:
    dq = deque(mod1+mod0+mod2)

if len(ans) == N:
    for i, g in enumerate(group):
        if g:
            ans[i] = dq.pop()
        else:
            ans[i] = dq.popleft()

# output
# print(group)
print(" ".join(map(str, ans)))
def main():
  N, M = [int(n) for n in input().split(" ")]

  if abs(N - M) > 2:
    print(0)
  elif abs(N - M) == 1:
    print((factorial(N) * factorial(M)) % 1000000007)
  else:
    print((factorial(N) * factorial(M) * 2) % 1000000007)

def factorial(n):
  if n > 1:
    return (n * factorial(n - 1)) % 1000000007
  else:
    return 1
    
main()

### FIXED CODE ###

def main():
  N, M = [int(n) for n in input().split(" ")]

  if abs(N - M) >= 2:
    print(0)
  elif abs(N - M) == 1:
    print((factorial(N) * factorial(M)) % 1000000007)
  else:
    print((factorial(N) * factorial(M) * 2) % 1000000007)

def factorial(n):
  ret = 1
  for i in range(1, n + 1):
    ret = (ret * i) % 1000000007
  return ret
    
main()
n = int(input())
l = list(map(int, input().split()))

cnt = 0
while all(a % 2 == 0 for a in A):
	A = [a / 2 for a in A]
    cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
count = 0
while all(a % 2 == 0 for a in A):
    A = [a / 2 for a in A]
    count += 1
print(count)
n = int(input())
print("Yes" if n%sum(map(int,n))==0 else "No")


### FIXED CODE ###

n = input()
print("Yes" if int(n)%sum(map(int,n))==0 else "No")
p = [(-1,2,4,1,3,-1),
     (3,-1,0,5,-1,2),
     (1,5,-1,-1,0,4),
     (4,0,-1,-1,5,1),
     (2,-1,5,0,-1,3),
     (-1,3,1,4,2,-1)]

d1 = list(map(int, input().split()))
top, front, right = d1[0], d1[1], d1[2]
d2 = list(map(int, input().split()))
d1 = {v: k for k, v in enumerate(d1)}
d2 = {v: k for k, v in enumerate(d2)}
boo = True if len(d1) == 6 and len(d2) == 6 else False
if boo:
    x, y = d2[top], d2[front]
    adjacent = {v: k for k, v in d2.items()}
    try:
        if right == adjacent[p[x][y]]:
            print("Yes")
        else:
            print("No")
    except KeyError:
        print("No")

else:
    d1 = [(k, v) for k, v in enumerate(d1)]
    d2 = [(k, v) for k, v in enumerate(d2)]
    for m in range(5, 1, -1):
        if d1[m][1] != d1[m-1][1]:
            x, y = d1[m][0], d1[m-1][0]
            t1, f1, r1 = d1[m][0], d1[m-1][0], d1[p[x][y]][0]
            break
        else:
            t1, f1, r1 = 0, 0, 0
    for m in range(5, 1, -1):
        if d2[m][1] != d2[m-1][1]:
            x, y = d2[m][0], d2[m-1][0]
            t2, f2, r2 = d2[m][0], d2[m-1][0], d2[p[x][y]][0]

    if t2 == r1 and r2 == t1:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

p = [(-1,2,4,1,3,-1),
     (3,-1,0,5,-1,2),
     (1,5,-1,-1,0,4),
     (4,0,-1,-1,5,1),
     (2,-1,5,0,-1,3),
     (-1,3,1,4,2,-1)]

d1 = list(map(int, input().split()))
top, front, right = d1[0], d1[1], d1[2]
d2 = list(map(int, input().split()))
da1 = {v: k for k, v in enumerate(d1)}
da2 = {v: k for k, v in enumerate(d2)}
boo = True if len(da1) == 6 and len(da2) == 6 else False
if boo:
    x, y = da2[top], da2[front]
    adjacent = {v: k for k, v in da2.items()}
    try:
        if right == adjacent[p[x][y]]:
            print("Yes")
        else:
            print("No")
    except KeyError:
        print("No")

else:
    db1 = [(k, v) for k, v in enumerate(d1)]
    db2 = [(k, v) for k, v in enumerate(d2)]
    for m in range(5, 1, -1):
        if db1[m][1] != db1[m-1][1]:
            x, y = db1[m][0], db1[m-1][0]
            t1, f1, r1 = db1[m][0], db1[m-1][0], db1[p[x][y]][0]
            break
        else:
            t1, f1, r1 = 0, 0, 0
    for m in range(5, 1, -1):
        if db2[m][1] != db2[m-1][1]:
            x, y = db2[m][0], db2[m-1][0]
            t2, f2, r2 = db2[m][0], db2[m-1][0], db2[p[x][y]][0]

    if t2 == r1 and r2 == t1:
        print("Yes")
    else:
        print("No")
H,W = map(int,input().split())

N = int(input())

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

s = []

res = []

for v,i in enumerate(a,1):
    for _ in range(v):
        s.append(str(i))

for i in range(H):
    for j in range(W):
        res.append(str(s.pop(0)))
    if i % 2 == 1:
        res.reverse()
    print(' '.join(res))
    res = []

### FIXED CODE ###

H,W = map(int,input().split())

N = int(input())

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

res = []
j = 0
st = 0 # リスト添え字管理

for i in range(H):
    j = 0
    while j < W:
        while 0 < a[st] and j < W:
            res.append(str(st+1))
            j += 1
            a[st] -= 1
        if a[st] == 0:
            st += 1
    if i % 2 == 1:
        res.reverse()
    print(' '.join(res))
    res = []
n = int(input())
XY = []
for i in range(n):
    a = int(input())
    xy = []
    for j in range(a):
        x, y = map(int, input().split())
        xy.append([x, y])
    XY.append(xy)
ans = 0
for i in range(2 ** n):
    s = [0] * n
    cnt = 0
    case = True
    for j in range(n):
        if (i >> j) & 1:
            s[n - 1 - j] = 1
            cnt += 1
    for k in range(n):
        if s[k] == 1:
            for l in range(len(XY[l])):
                if s[XY[k][l][0] - 1] != XY[k][l][1]:
                    case = False
    if case is True:
        ans = max(ans, cnt)
print(ans)

### FIXED CODE ###

n = int(input())
XY = []
for i in range(n):
    a = int(input())
    xy = []
    for j in range(a):
        x, y = map(int, input().split())
        xy.append([x, y])
    XY.append(xy)
ans = 0
for i in range(2 ** n):
    s = [0] * n
    cnt = 0
    case = 0
    for j in range(n):
        if (i >> j) & 1:
            s[n - 1 - j] = 1
            cnt += 1
    for k in range(n):
        if s[k] == 1:
            for l in range(len(XY[k])):
                if s[XY[k][l][0] - 1] != XY[k][l][1]:
                    case = 1
    if case == 0:
        ans = max(ans, cnt)
print(ans)
# C
n,k=map(int,input().split())
print((n+k-3)//(k-1))

### FIXED CODE ###

# A
s = str(input())
result = 0
for c in list(s):
    if c == '+':
        result += 1
    else:
        result -= 1
print(result)
import bisect
n=int(input())
a=list(map(int,input().split()))
la=[0,0,0,0]
for i in range(n):
    la.append(la[i]+a[i])
sa = la[-1]
ma = sa // 2
def ans(r):
    return max(r) - min(r)
def ans2(r1,r2,r3,r4):
    return max(r1,r2,r3,r4) - min(r1,r2,r3,r4)

ca = bisect.bisect_left(la,ma)

ha1 = la[:ca]
ha2 = la[ca:]

cha1 = bisect.bisect_left(ha1,ha1[-1]//2)
r1=[0,0]
r1[0] = ha1[cha1]
r1[1] = ha1[-1] - r1[0]
r2=[0,0]
r2[0] = ha1[cha1-1]
r2[1] = ha1[-1] - r2[0]

tminus = ha1[-1]
for i in range(len(ha2)):
    ha2[i] -= tminus
cha2 = bisect.bisect_left(ha2,ha2[-1]//2)
r3=[0,0]
r3[0] = ha2[cha2]
r3[1] = ha2[-1] - r3[0]
r4=[0,0]
r4[0] = ha2[cha2-1]
r4[1] = ha2[-1] - r4[0]

res1 = min(ans(r1+r3),ans(r1+r4),ans(r2+r3),ans(r2+r4))

ha1 = la[:ca-1]
ha2 = la[ca-1:]

cha1 = bisect.bisect_left(ha1,ha1[-1]//2)
r1=[0,0]
r1[0] = ha1[cha1]
r1[1] = ha1[-1] - r1[0]
r2=[0,0]
r2[0] = ha1[cha1-1]
r2[1] = ha1[-1] - r2[0]

tminus = ha1[-1]
for i in range(len(ha2)):
    ha2[i] -= tminus
cha2 = bisect.bisect_left(ha2,ha2[-1]//2)
r3=[0,0]
r3[0] = ha2[cha2]
r3[1] = ha2[-1] - r3[0]
r4=[0,0]
r4[0] = ha2[cha2-1]
r4[1] = ha2[-1] - r4[0]

res2 = min(ans(r1+r3),ans(r1+r4),ans(r2+r3),ans(r2+r4))

ha1 = la[:ca+1]
ha2 = la[ca+1:]

cha1 = bisect.bisect_left(ha1,ha1[-1]//2)
r1=[0,0]
r1[0] = ha1[cha1]
r1[1] = ha1[-1] - r1[0]
r2=[0,0]
r2[0] = ha1[cha1-1]
r2[1] = ha1[-1] - r2[0]

tminus = ha1[-1]
for i in range(len(ha2)):
    ha2[i] -= tminus
cha2 = bisect.bisect_left(ha2,ha2[-1]//2)
r3=[0,0]
r3[0] = ha2[cha2]
r3[1] = ha2[-1] - r3[0]
r4=[0,0]
r4[0] = ha2[cha2-1]
r4[1] = ha2[-1] - r4[0]

res3 = min(ans(r1+r3),ans(r1+r4),ans(r2+r3),ans(r2+r4))


print(min(res1,res2,res3))

### FIXED CODE ###

import bisect
INF = 10**16
n=int(input())
a=list(map(int,input().split()))
la=[0]
for i in range(n):
    la.append(la[i]+a[i])
la.pop(0)
sa = la[-1]
l=0
r=2
res = INF
for i in range(1,n-2):
    while abs(la[l+1]-(la[i]-la[l+1])) < abs(la[l]-(la[i]-la[l])):
        l += 1

    if r == i:
        r += 1
    while abs((la[r+1] - la[i])-(sa - la[r+1])) < abs((la[r] - la[i])-(sa - la[r])):
        r += 1
    r1 = la[l]
    r2 = la[i] - la[l]
    r3 = la[r] - la[i]
    r4 = sa    - la[r]
    res=min(res,max(r1,r2,r3,r4)-min(r1,r2,r3,r4))
print(res)
s = input()
 
for i in range(len(s)):
    if s[i] == '?':
        if i == 0 and s[1] == 'D':
            s = s.replace('?','P',1)
        elif i == 0 and s[1] == 'P':
            s = s.replace('?','D',1)
        elif i == 0 and s[1] == '?':
            s = s.replace('?','D',1)
        elif s[i-1] =='P':
            s = s.replace('?','D',1)
        elif s[i-1] =='D' and (i ==len(s)-1):
            s = s.replace('?','D',1)
        elif s[i-1] =='D' and (s[i+1] == 'P' or s[i+1] == '?'):
            s = s.replace('?','D',1)
        else:
            s = s.replace('?','P',1)


print(s)

### FIXED CODE ###

s = input()
 
for i in range(len(s)):
    if s[i] == '?':
        if i == 0 and len(s) == 1:
            s = s.replace('?','D',1)
        elif i == 0 and s[1] == 'D':
            s = s.replace('?','P',1)
        elif i == 0 and s[1] == 'P':
            s = s.replace('?','D',1)
        elif i == 0 and s[1] == '?':
            s = s.replace('?','D',1)
        elif s[i-1] =='P':
            s = s.replace('?','D',1)
        elif s[i-1] =='D' and (i ==len(s)-1):
            s = s.replace('?','D',1)
        elif s[i-1] =='D' and (i <len(s)-1 and(s[i+1] == 'P' or s[i+1] == '?')):
            s = s.replace('?','D',1)
        else:
            s = s.replace('?','P',1)


print(s)
while True:
    h,w = map(int,input().split())
    if h == 0 and w == 0:
        break
    for i in range(h)
        print("#" * w)
    print("")

### FIXED CODE ###

while True:
    h,w = map(int,input().split())
    if h == 0 and w == 0:
        break
    for i in range(h):
        print("#"*w)
    print("")
import collections
import copy
import math
import scipy.special import comb

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
nums = [ int(s) for s in input().split() ]


for i in range(n):
    ans = 0

    cpl = copy.copy(nums)
    cpl.pop(i)
    ct = collections.Counter(cpl)

    for key, val in ct.items():
        if val > 1:
            ans += comb(val, 2, exact=True)
    
    print(ans)


### FIXED CODE ###




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

# counter
from collections import Counter
cntr = Counter(lst)

# combination
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

total = 0
# countSameNames
for value in cntr.values():
    if value > 1:
        total += combinations_count( value, 2 )


for l in lst:
    print(total - (cntr[l]-1))
n=int(input("n?"))
k=int(input("k?"))
a=[int(input("a?")) for i in range(n)]
sei=[0]*(n-k+1)
for i in range(n-k+1):
  for j in range(i,i+k):
    sei[i]+=a[j]

for i in range(n-k):
  if sei[i]<sei[i+1]:
    print("yes")
  else:
    print("no")

### FIXED CODE ###

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

for i in range(n-k):

  if  a[i]<a[i+k]:
    print("Yes")
  else:
    print("No")
import math

N = int(input())
ints = list(map(int, input().split()))
ints.sort(reverse=True)

gcd = 0
result = 1
holed_ints = []
for i in range(N):
    holed_ints = ints[:i] + ints[i+1:]
    gcd = 0
    for j in range(N-1):
        gcd = math.gcd(gcd, holed_ints[j])
        if gcd == 1:
            break
    if gcd > result:
        result = gcd

print(result)

### FIXED CODE ###

import fractions

integral_count = int(input())
blackboard_integers = list(map(int, input().split()))

gcd_integers = list(set(blackboard_integers))

gcd = 0
result = 1
for i in range(len(gcd_integers)):
    gcd = 0
    if blackboard_integers.count(gcd_integers[i]) >= 2:
        for n in gcd_integers:
            gcd = fractions.gcd(gcd, n)
    else:
        for n in gcd_integers[:i]:
            gcd = fractions.gcd(gcd, n)
        for n in gcd_integers[i+1:]:
            gcd = fractions.gcd(gcd, n)
    if gcd > result:
        result = gcd

print(result)
K = int(input())
a1 = 7
ai = 0
for i in range(K + 1):
        ai = a1 % K
        a1 = (a1 * 10 + 7)
    if ai == 0:
        break
 
print(i + 1)

### FIXED CODE ###

K = int(input())
a1 = 7
ai = 0
for i in range(K + 1):
  if i == 0:
    ai = a1 % K
  else:
    ai = (ai * 10 + 7) % K
  if ai == 0:
    break
else:
    i = -2
print(i + 1)
print('ABC' + input())print('ABC' + input())

### FIXED CODE ###

print('ABC' + input())
import sys
data = list(input())
for i, _str in enumerate(data):
  if _str == "?":
    if i == 0:
      if data[i + 1] == "D":
        data[i] = "P"
      else:
        data[i] = "D"
    elif i == len(data) - 1:
      if data[i - 1] == "D":
        data[i] = "P"
      else:
        data[i] = "D"
    else:
      if data[i - 1] == "D" or data[i + 1] == "D":
        data[i] = "P"
      else:
        data[i] = "D"
ans = "".join(data)
print(ans)

### FIXED CODE ###

import sys
data = list(input())
for i, _str in enumerate(data):
  if _str == "?":
    data[i] = "D"
ans = "".join(data)
print(ans)
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while (p<n and a[q]+a[p]<=md):
            p+=1
    except:
        p=n

    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)

### FIXED CODE ###

def f(i):
    return i
s,t=map(f,input().split())
print(t+s)
ll A, B, C, X, Y;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B >> C >> X >> Y;
    
    ll ans = infl;
    rep(ab, 0, 201010) {
        ll sm = C * ab;
 
        ll x = X - ab / 2;
        ll y = Y - ab / 2;
 
        if (0 < x) sm += x * A;
        if (0 < y) sm += y * B;
 
        chmin(ans, sm);
    }
 
    cout << ans << endl;
}

### FIXED CODE ###

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

res = a*x + b*y # 条件を満たす買い方のうちABピザの枚数(*2)を全探索する。ABピザを一切買わない場合を一旦答えにする（これを大きい値にして、for ループを0からにしてもよい）
for i in range(1, max(x, y)+1): # 全部ABピザでまかなう時は x,yの内多い方分買うことになる
    ab = i*2 # ABピザを買う枚数奇数枚買うことはないので2倍
    cand = ab*c + a*max(0, x-i) + b*max(0, y-i) # i枚分はABピザになるので-i 負の値にはならない（あまりになる）ので0とのmaxをとる

    res = min(res, cand) # 候補との最小値を保持

print(res)
import fraction
from functools import reduce

def gcd(*numbers):
    return reduce(fraction.gcd, numbers)

def gcd_list(numbers):
    return reduce(fraction.gcd, numbers)

N = int(input())

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


print(gcd_list(a))

### FIXED CODE ###

import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

N = int(input())

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


print(gcd_list(a))
n, m, l = [int(i) for i in input().split()]

A = []
B = []
C = []

for ni in range(n):
    A.append([int(i) for i in input().split()])

for mi in range(m):
    B.append([int(i) for i in input().split()])

for i in range(n):
    C.append([])
    for j in range(l):
        C[i].append(0)
        for k in range(m):
            C[i][j] += A[i][k] * B[k][j]
for li in range(l):
    print(" ".join([str(s) for s in C[ni]))

### FIXED CODE ###

n, m, l = [int(i) for i in input().split()]

A = []
B = []
C = []

for ni in range(n):
    A.append([int(i) for i in input().split()])

for mi in range(m):
    B.append([int(i) for i in input().split()])

for i in range(n):
    C.append([])
    for j in range(l):
        C[i].append(0)
        for k in range(m):
            C[i][j] += A[i][k] * B[k][j]
for ni in range(n):
    print(" ".join([str(s) for s in C[ni]]))
a, b = (map(int, input().split()))
if (a <= b):
    print(a)
else:
    print(a-1

### FIXED CODE ###

a, b = map(int, input().split())
if (a <= b):
    print(a)
else:
    print(a-1)