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

import sys

sys.setrecursionlimit(100000)


def check(i, xs, checked):
    xi = xs[i]
    children = set()
    for j, d in links[i]:
        if j in checked:
            continue
        xj = xs[j]
        if xj is None:
            xs[j] = xi + d
        elif xi + d != xj:
            return False
        children.add(j)
    checked.add(i)
    for jc in children:
        if not check(jc, xs, checked):
            return False
    return True


def solve():
    checked = set()
    for i in range(n):
        if i not in checked:
            xs = [None] * n
            xs[i] = 0
            res = check(i, xs, checked)
            if not res:
                return False
            xf = [x for x in xs if x is not None]
            mn, mx = min(xf), max(xf)
            if mx - mn > 1e9:
                return False
    return True


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    links[l].add((r, d))
    links[r].add((l, -d))
print('Yes' if solve() else 'No')


### FIXED CODE ###

import sys

sys.setrecursionlimit(100000)


def check(i, xs, checked):
    xi = xs[i]
    children = set()
    for j, d in links[i]:
        if checked[j]:
            continue
        if j not in xs:
            xs[j] = xi + d
        elif xi + d != xs[j]:
            return False
        children.add(j)
    checked[i] = True
    for j in children:
        if not check(j, xs, checked):
            return False
    return True


def solve():
    checked = [False] * n
    for i in range(n):
        if not checked[i]:
            xs = {}
            xs[i] = 0
            res = check(i, xs, checked)
            if not res:
                return False
            mn, mx = min(xs.values()), max(xs.values())
            if mx - mn > 1e9:
                return False
    return True


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    links[l].add((r, d))
    links[r].add((l, -d))
print('Yes' if solve() else 'No')
### BUGGY CODE ###

I=9**9
def S():
 h,a,*m=open(0)
 h,w,k,a,b,f,g=map(int,(h+a).split())
 d=[I]*h*w
 a=~w+a*w+b
 d[a]=1
 q=[a]
 for s in q:
  for y,x in(1,0),(-1,0),(0,1),(0,-1):
   for z in range(k):
    i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
    if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
    q+=t,;d[t]=d[s]+1
 print(d[~w+f*w+g]%I-1)
S()

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
a = LIST()

lim = 3001
dp = [[0]*lim for _ in range(lim)]
cnt = 0
for i in range(1, N+1):
	for l in range(N-i+1):
		cnt += 1
		r = l+i
		if (N-i)%2: #後手
			dp[l][r] = min(dp[l+1][r]-a[l], dp[l][r-1]-a[r-1])
		else: #先手
			dp[l][r] = max(dp[l+1][r]+a[l], dp[l][r-1]+a[r-1])

print(dp[0][N])


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
a = LIST()

lim = 3001
dp = [[0]*lim for _ in range(lim)]
cnt = 0
for i in range(1, N+1):
	for l in range(N-i+1):
		cnt += 1
		r = l+i
		if (N-i)%2: #後手
			dp[l][r] = min(dp[l+1][r]-a[l], dp[l][r-1]-a[r-1])
		else: #先手
			dp[l][r] = max(dp[l+1][r]+a[l], dp[l][r-1]+a[r-1])

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

num_list = [int(i) for i in input().split()]

result = 0

max = num_list[0] * num_list[1]
for i in range(1, max + 1):
    amari_1 = i % num_list[0]
    amari_2 = i % num_list[1]
    if amari_1 == 0 and amari_2 == 0:
        result = i
        break

print(result)


### FIXED CODE ###

num_list = [int(i) for i in input().split()]

result = 0

if num_list[0] < num_list[1]:
    A = num_list[0]
    B = num_list[1]
else:
    A = num_list[1]
    B = num_list[0]

while True:
    amari = A % B
    if amari == 0:
        break
    A = B
    B = amari

#最大公約数 B

#最小公倍数
result =  num_list[0] * num_list[1] // B

print(result)
### BUGGY CODE ###

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

Lists=[]
moto=0
for i in range(n):
    Lists.append(a.count(i+1))
    if ((Lists[i]>1)):
        moto+=Lists[i]*(Lists[i]-1)//2
#print(a)
#print(Lists)
#print(moto)
#print(Lists)
for i in range(n):
    if (Lists[a[i]-1]>1):
        ans=moto+1-Lists[a[i]-1]
    else:
        ans=moto
    print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
List={}
x=0
for i in range(n):
    if not a[i] in List:
        List[a[i]] = 1
    else:
        List[a[i]]+=1
    
sigma=0

for key,item in List.items():
    sigma += item*(item-1)//2
for i in range(n):
    print(sigma-List[a[i]]+1)
### BUGGY CODE ###

n,p=map(int,input().split())
if n==1:
    print(p)
    exit()
import math 
use=math.ceil(p**(1/n))
while True :
    if p%(use**n)==0:
        print(use)
        break
    use-=1  

### FIXED CODE ###

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

if N == 1:
    ans = P
else:
    ans = 1
    p = 2
    while p * p <= P:
        e = 0
        while P % p == 0:
            P //= p
            e += 1  # 素数のカウント
        if e // N > 0:
            ans *= p ** (e // N)
        p += 1

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

from collections import defaultdict
from heapq import heappop, heappush
import sys
input=sys.stdin.readline 

class Graph:
 
    def __init__(self):
        self.graph = defaultdict(list)
        self.vertices = set()
        self.edges = []
 
    def add_edge(self, a, b, weight=1):
        self.graph[a].append((b, weight))
        self.vertices |= {a, b}
        self.edges.append((a, b, weight))
 
    def get_vertices(self):
        return sorted(list(self.vertices))
 
    def num_of_vertices(self):
        return len(self.vertices)
 
    def get_edges(self):
        return self.edges
 
    def num_of_edges(self):
        return len(self.edges)
 
class Dijkstra:
 
    def __init__(self, graph, start):
        self.g = graph.graph
 
        self.dist = defaultdict(lambda: float("inf"))
        self.dist[start] = 0
 
        self.prev = defaultdict(lambda: None)
 
        self.Q = []
        heappush(self.Q, (0, start))
 
        while self.Q:
            dist_u, u = heappop(self.Q)
 
            if self.dist[u] < dist_u:
                continue
 
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))
 
 
    def shortest_distance(self, goal):
 
        return self.dist[goal]
 
    def shortest_path(self, goal):
 
        path = []
        vertice = goal
        cnt = 0
        while vertice is not None:
            path.append(vertice)
            cnt += 1
            vertice = self.prev[vertice]
 
        return path, cnt

N, M = map(int, input().split())
G = Graph()
T = []
C = defaultdict(int)
for _ in range(M):
    a, b, c = map(int, input().split())
    G.add_edge(a, b, c)
    G.add_edge(b, a, c)
    T.append(tuple(sorted([a, b])))

for i in range(1, N+1):
    for j in range(1, N+1):
        D = Dijkstra(G, i)
        P, L = D.shortest_path(j)
        for k in range(L-1):
            a, b = P[k], P[k+1]
            C[tuple(sorted([a, b]))] = 1

ans = 0
for a, b in T:
    if C[(a, b)] == 0:
        ans += 1

print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
inf = float("inf")
dist = [[inf for _ in range(N)] for _ in range(N)]
for i in range(N):
    dist[i][i] = 0

T = []
for i in range(M):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    T.append((a, b, c))
    dist[a][b] = min(dist[a][b], c)
    dist[b][a] = min(dist[b][a], c)

for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])

ans = M
for a, b, c in T:
    check = False
    for i in range(N):
        if dist[i][a] + c == dist[i][b]:
            check = True
    if check:
        ans -= 1
print(ans)
### BUGGY CODE ###

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

B=list(itertools.combinations(A, 2))
SUM=0

for b1, b2 in B:
  SUM += b1^b2

print(SUM%(10**9+7))

### FIXED CODE ###

import numpy as np
 
n = int(input())
arr = np.array([int(i) for i in input().split()])
mod = 10 ** 9 + 7
ans = 0
 
for i in range(60):
    #一桁目が1か0か調べて1の個数をカウント
    c1 = np.count_nonzero(arr & 1) 
    #1の個数×0の個数(XORだから)
    ans += 2 ** i * c1 * (n - c1)
    #桁をシフト
    arr =arr >> 1

print(ans % mod)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def meguru_bisect(is_ok, left, right):
        """
        :param is_ok: 定義して下さい
        :param left: 取りうる最小の値-1
        :param right: 取りうる最大の値+1
        :return: is_okを満たす最小(もしくは最大)の値
        """
        while abs(left - right) > 1:
            mid = (left + right) // 2
            if is_ok(mid):
                right = mid
            else:
                left = mid
        return right

    def is_ok(x):
        total = 0
        for i in range(n):
            total += max(0, A[i] - x // F[i])
        return total <= k

    n, k = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    F = sorted(list(map(int, input().split())), reverse=True)

    left = -1
    right = 10 ** 12 + 1
    res = meguru_bisect(is_ok, left, right)
    print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
a = np.array(input().split(), np.int64)
f = np.array(input().split(), np.int64)
a.sort()
f.sort()
a = a[::-1]
left = -1
right = np.max(a * f)
while left + 1 < right:
    mid = (left + right) // 2
    if np.sum(np.maximum(a - mid // f, 0)) <= k:
        right = mid
    else:
        left = mid

print(right)
### BUGGY CODE ###

N=int(input())
S = input()
l, r = 0, N

def pow_mod(a, b, m):
  ab = 1
  for _ in range(b):
    ab = (ab * a) % m
  return ab

def c2n(c):
  return ord(c) - 97

def hash(s, B, H):
  sh = 0
  for c in s:
    sh = (sh * B + c2n(c)) % H
  return sh

def find_rolling_hash(s, t):
  B, H = 10 ** 8 + 7, 2 ** 64

  sl, tl = len(s), len(t)
  if sl > tl:
    return False
  Bsl = pow_mod(B, sl, H)
  sh, cth = hash(s, B, H), hash(t[:sl], B, H)
  if sh == cth:
    return True
  for i in range(tl - sl):
    cth = (cth * B - c2n(t[i]) * Bsl + c2n(t[i+sl])) % H
    if sh == cth:
      return True
  return False

def t(n):
  for i in range(0, N-n):
    s = S[i:i+n]
    if find_rolling_hash(s, S[i+n:]):
      return True
  return False

while l+1<r:
  m = (l+r)//2
  if t(m):
    l=m
  else:
    r=m

print(l)

### FIXED CODE ###

import random
import string
N = int(input())
S = input()
l, r = 0, N

def pow_mod(a, b, m):
  ab = 1
  for _ in range(b):
    ab = (ab * a) % m
  return ab

def c2n(c):
  return ord(c) - 97

def hash(s, B, H):
  sh = 0
  for c in s:
    sh = (sh * B + c2n(c)) % H
  return sh

def t(n):
  B, H = 10 ** 8 + 7, 2 ** 64

  if n*2 > N:
    return False
  s, t = S[:n], S[n:n*2]
  sh, th = hash(s, B, H), hash(t, B, H)
  if sh == th:
    return True
  ss = set([sh])
  Bn = pow_mod(B, n, H)
  for i in range(0, N-2*n):
    sh = (sh * B - c2n(S[i]) * Bn + c2n(S[i+n])) % H
    th = (th * B - c2n(S[i+n]) * Bn + c2n(S[i+2*n])) % H
    ss.add(sh)
    if th in ss:
      return True
  return False

while l+1<r:
  m = (l+r)//2
  if t(m):
    l=m
  else:
    r=m

print(l)
### BUGGY CODE ###

N,K = map(int, input().split())
A = [int(x)-1 for x in map(int, input().split())]

l = []
place = 0
while True:
    if K==0:
        print(place+1)
        exit()
    l.append(place)
    place = A[place]
    K -= 1
    if place in l:
        count = len(l) - l.index(place)
        print(l[l.index(place) + K%count]+1)
        exit()

### FIXED CODE ###

N,K = map(int, input().split())
A = [int(x)-1 for x in map(int, input().split())]
flag = [False]*N
l = []
place = 0
while True:
    if K==0:
        print(place+1)
        exit()
    l.append(place)
    flag[place]=True
    place = A[place]
    K -= 1
    if flag[place]:
        ind = l.index(place)
        count = len(l) - ind
        print(l[ind + K%count]+1)
        exit()
### BUGGY CODE ###

from fractions import gcd

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

m = gcd(A, B)
pf = []
for i in range(2, m+1):
    if m % i == 0:
        pf.append(i)
    while m % i == 0:
        m //= i
if m != 1:
    pf.append(m)

print(len(pf) + 1)

### FIXED CODE ###

from fractions import gcd

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

m = gcd(A, B)
pf = []
for i in range(2, m+1):
    if i ** 2 > m:
        break
    if m % i == 0:
        pf.append(i)
    while m % i == 0:
        m //= i
if m != 1:
    pf.append(m)
    
print(len(pf) + 1)
### BUGGY CODE ###

N=int(input())
print(min([max([len(str(i)),len(str(int(N/i)))]) for i in range(1,N+1) if N%i==0]))


### FIXED CODE ###

N=int(input())
M=int((N**(1/2)))
mult=0
while 1:
    for i in [-1,1]:
        x=M+i*mult
        if not N%x:
            print(max([len(str(x)),len(str(int(N/x)))]))
            exit()
    mult+=1
### BUGGY CODE ###

import math
k=int(input())
ans=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for h in range(1,k+1):
      ans+=math.gcd(math.gcd(i,j),h)
print(ans)

### FIXED CODE ###

import math
k=int(input())
ans=0
for i in range(1,k+1):
  for j in range(1,k+1):
    tmp=math.gcd(i,j)
    for h in range(1,k+1):
      ans+=math.gcd(tmp,h)
print(ans)
### BUGGY CODE ###

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

l = []
cnt = 0
for i in range(n):
  if not a[i] in l:
    tmp = a.count(a[i])
    if a[i] > tmp:
      cnt = cnt + tmp
    elif a[i] < tmp:
      cnt = cnt + tmp - a[i]
    l.append(a[i])
print(cnt)

### FIXED CODE ###

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

d = {}
for ai in a:
  if ai in d:
    d[ai] = d[ai] + 1
  else:
    d[ai] = 1

cnt = 0
for key, value in d.items():
  if key > value:
    cnt = cnt + value
  elif key < value:
    cnt = cnt + value - key

print(cnt)
### BUGGY CODE ###

import math 
N,K=map(int,input().split())
A=[int(x) for x in input().split()]
A=sorted(A)
left=0
right=max(A)
mid=max((left+right)//2,1)

while(right-left>=1):
    numofcut=0
    
    for i in range(N):
        if A[i]%mid==0:
            numofcut+=(A[i]//mid) -1
        else:
            numofcut+=A[i]//mid
    #print(numofcut)
    if numofcut>K:
        left=mid+1
    else:
        right=mid
    mid=max((left+right)//2,1)

print(mid)

### FIXED CODE ###

import math 
N,K=map(int,input().split())
A=[int(x) for x in input().split()]
A=sorted(A)
left=0
right=max(A)
mid=max((left+right)//2,1)

while(right-left>=1):
    numofcut=0
    
    for i in range(N):
        if A[i]%mid==0:
            numofcut+=(A[i]//mid) -1
        else:
            numofcut+=A[i]//mid
    #print(numofcut)
    if numofcut>K:
        left=mid+1
    else:
        right=mid
    mid=max((left+right)//2,1)
    if mid==1:
        break
print(mid)
### BUGGY CODE ###

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

mod = 10**18
ans = 1
for i in range(N):
    ans *= A[i]

if ans > mod:
    print(-1)
    exit()

print(ans)

### FIXED CODE ###

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

mod = 10**18
ans = 1
for i in range(N):
    ans *= A[i]
    if ans > mod:
        if 0 in A:
            print(0)
        else:
            print(-1)
        exit()

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

import copy
def hashnum(state):
    num = 0
    for i in range(3):
        for j in range(3):
            num *= 10
            num += state[i][j]
    return num

answer = 123456780
ini_state = []
for i in range(3):
    temp = [int(n) for n in input().split(" ")]
    if 0 in temp:
        zero_x, zero_y = temp.index(0), i
    ini_state.append(temp)
queue = [[ini_state, zero_x, zero_y]]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = set()
visited |= {hashnum(ini_state)}
trial = 0
while answer not in visited:
    new_queue = []
    trial += 1
    for q in queue:
        state, zero_x, zero_y = q
        for i in range(len(dx)):
            new_state = copy.deepcopy(state)
            new_x = zero_x + dx[i]
            new_y = zero_y + dy[i]
            if 0 <= new_x < 3 and 0 <= new_y < 3:
                new_state[new_y][new_x], new_state[zero_y][zero_x] = new_state[zero_y][zero_x], new_state[new_y][new_x]
                perm = hashnum(new_state)
                if perm == answer:
                    print(trial)
                    exit()
                if perm not in visited:
                    visited |= {perm}
                    new_queue.append([new_state, new_x, new_y])
    queue = new_queue
    
# print(trial)

### FIXED CODE ###

import copy
def hashnum(state):
    num = 0
    for i in range(3):
        for j in range(3):
            num *= 10
            num += state[i][j]
    return num

answer = 123456780
ini_state = []
for i in range(3):
    temp = [int(n) for n in input().split(" ")]
    if 0 in temp:
        zero_x, zero_y = temp.index(0), i
    ini_state.append(temp)
end_state = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
queue = [[ini_state, zero_x, zero_y, 0], [end_state, 2, 2, 1]]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = {}
if hashnum(ini_state) == answer:
    print(0)
else:
    visited[hashnum(ini_state)] = [0, 0]
    visited[answer] = [0, 1]
    trial = 0
    ended = 0
    while queue:
        new_queue = []
        trial += 1
        for q in queue:
            if ended:
                break
            state, zero_x, zero_y, direction = q
            for i in range(len(dx)):
                new_state = copy.deepcopy(state)
                new_x = zero_x + dx[i]
                new_y = zero_y + dy[i]
                if 0 <= new_x < 3 and 0 <= new_y < 3:
                    new_state[new_y][new_x], new_state[zero_y][zero_x] = new_state[zero_y][zero_x], new_state[new_y][new_x]
                    perm = hashnum(new_state)
                    if perm in visited and direction != visited[perm][1]:
                        print(trial + visited[perm][0])
                        ended = 1
                        break
                    elif perm not in visited:
                        visited[perm] = [trial, direction]
                        new_queue.append([new_state, new_x, new_y, direction])
        queue = new_queue
### BUGGY CODE ###

import math
import sys

n, m = map(int, input().split())
a_list = [-1]
for _ in range(m):
    a_list.append(int(input()))
a_list.append(n + 1)

fact_memo = dict()
def fact(n):
    if n in fact_memo.keys():
        return fact_memo[n]
    f = math.factorial(n)
    fact_memo[n] = f
    return f

memo = dict()
ans = 1
cur = a_list[0]
for i, a in enumerate(a_list):
    if i == 0:
        continue
    sub = a - cur - 1
    cur = a
    if sub <= 2:
        if sub == 0:
            print(0)
            sys.exit()
        continue
    sub -= 1
    if sub in memo.keys():
        ans *= memo[sub]
        continue
    count = 0
    for j in range(sub // 2 + 1):
        count += fact(sub - j) // fact(j) // fact(sub - j * 2)
    memo[sub] = count
    ans *= count
print(ans % 1000000007)


### FIXED CODE ###

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

N, M = map(int, readline().split())
ans = [0] * (N + 2)
ans[0] = 1
for _ in range(M):
    a = int(readline())
    ans[a] = -1

for i in range(1, N + 1):
    if ans[i] == -1:
        continue
    a1 = max(ans[i - 2], 0)
    a2 = max(ans[i - 1], 0)
    ans[i] = a1 + a2

print(ans[N] % (10 ** 9 + 7))
### BUGGY CODE ###

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

n = int(input())
i = floor(sqrt(n))
dis = 0
while True:
    f = i / n
    j = floor(f)
    if f - j > 0:
        dis += 1
        continue
    print(i + j)
    sys.exit()

### FIXED CODE ###

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

n = int(input())
for i in range(ceil(sqrt(n)), 0, -1):
    f = n / i
    j = floor(f)
    if f - j > 0: continue
    print(i + j - 2)
    sys.exit()