Harryxun/stf_run huggingface dataset:
N,u,v = map(int,input().split())
u -= 1
v -= 1

du = [0]*N
dv = [0]*N
du[u] = 0
dv[v] = 0
G = [[]]*N

def dfs(v, d, p, dis):
    dis[v] = d
    if G[v] != []:
        for u in G[v]:
            if( u == p):
                continue
            else:
                dfs( u, d+1, v, dis )

def calcDist(s, dist):
    dfs(s, 0, -1, dist)

for i in range(N-1):
    e1,e2 = map(int, input().split())
    e1 -= 1
    e2 -= 1
    if G[e1] == []:
        G[e1] = [e2]
    else:
        G[e1].append(e2)
    if G[e2] == []:
        G[e2] = [e1]
    else:
        G[e2].append(e1)

if v in G[u]:
    ans = 0
else:    

    calcDist(v,dv)
    calcDist(u,du)
    maxD = 0
    for idu,idv in zip(du,dv):
        if idu < idv:
            maxD = max(maxD, idv)       
    ans = maxD-1
    
print(ans)

### FIXED CODE ###

import heapq

N,u,v = map(int,input().split())
u -= 1
v -= 1

#du = [0]*N
#dv = [0]*N
du = [float('inf')]*N
dv = [float('inf')]*N
#du[u] = 0
#dv[v] = 0
q = []

G = [[]]*N

'''
def dfs(v, d, p, dis):
    dis[v] = d
    if G[v] != []:
        for u in G[v]:
            if( u == p):
                continue
            else:
                dfs( u, d+1, v, dis )

def calcDist(s, dist):
    dfs(s, 0, -1, dist)
'''
def calcDist(s, dist):
    heapq.heappush(q,[0, s])
    dist[s] = int(0)
    
    while q!=[]:
        p = heapq.heappop(q)
        pv = p[1]
        if dist[pv] < p[0] :
            continue
        for i in range(len(G[pv])):
            eto = G[pv][i]
            if dist[eto] > dist[pv] + 1:
                 dist[eto] = int(dist[pv] + 1)
                 heapq.heappush(q, [dist[eto], eto])


for i in range(N-1):
    e1,e2 = map(int, input().split())
    e1 -= 1
    e2 -= 1
    if G[e1] == []:
        G[e1] = [e2]
    else:
        G[e1].append(e2)
    if G[e2] == []:
        G[e2] = [e1]
    else:
        G[e2].append(e1)

if v in G[u]:
    ans = 0
else:    

    calcDist(v,dv)
    calcDist(u,du)
    maxD = 0
    for idu,idv in zip(du,dv):
        if idu < idv:
            maxD = max(maxD, idv)       
    ans = maxD-1
    
print(ans)
import numpy as np


def is_prime(n):
    return n != 1 and not np.any(n % np.arange(2, n) == 0)


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

N = np.arange(1, min(A, B))

if N.size == 0:
    print(1)
else:
    cd = np.argwhere((A % N == 0) & (B % N == 0)).ravel() + 1
    primes = [n for n in cd if is_prime(n)]

    print(len(primes) + 1)


### FIXED CODE ###

from fractions import gcd


def prime_factors(n):
    i = 2

    factors = []

    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)

    return factors


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

print(len(set(prime_factors(gcd(A, B)))) + 1)
x = int(input())
a = int(input())
b = int(input())
X -= a
k = X//b
print(X - b*k)

### FIXED CODE ###

X = int(input())
a = int(input())
b = int(input())
X -= a
k = X//b
print(X - b*k)
def a(n):
    if n < 2:
        return 1
    return a(n-1) * n

n, m = map(int, input().split())
if abs(n-m) > 1:
    print(0)
elif abs(n-m) == 1:
    print(a(n) * a(m) % 1000000007)
else:
    print(2 * a(n) * a(m) % 1000000007)

### FIXED CODE ###

import math

n, m = map(int, input().split())
if abs(n-m) == 0:
    print(2*math.factorial(n)*math.factorial(m) % 1000000007)
elif abs(n-m) == 1:
    print(math.factorial(n)*math.factorial(m) % 1000000007)
else:
    print(0)
n,a,d=map(int,input().split())

dic={}

ans=0
for k in range(n+1):
    l=k*a+k*(k-1)*d//2
    r=l+k*(n-k)*d
    idx=l%d
    l//=d
    r//=d
    print(l,r,idx)
    if idx in dic:
        prel,prer=dic[idx]
        #共通部分ありか、なしかで分岐
        if prer<l or prel>r:
            dic[idx]=(l,r)
            ans+=r-l+1 
        else:
            nl=min(prel,l)
            nr=max(prer,r)
            ans+=prel-nl+nr-prer
            dic[idx]=(nl,nr)
    else:
        ans+=r-l+1 
        dic[idx]=(l,r)
print(ans)

### FIXED CODE ###

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

dic={}

ans=0

if d==0:
    if a==0:
        print(1)
    else:
        print(n+1)
else:
    for k in range(n+1):
        l=k*a+k*(k-1)*d//2
        r=l+k*(n-k)*d
        idx=l%d
        l//=d
        r//=d
        if idx in dic:
            prel,prer=dic[idx]
            #共通部分ありか、なしかで分岐
            if prer<l or prel>r:
                dic[idx]=(l,r)
                ans+=r-l+1 
            else:
                nl=min(prel,l)
                nr=max(prer,r)
                ans+=prel-nl+nr-prer
                dic[idx]=(nl,nr)
        else:
            ans+=r-l+1 
            dic[idx]=(l,r)
    print(ans)
import numpy as np
import math
while True:
    n=input()
    if n==0: break
    s=map(int,raw_input().split())
    var=np.var(s)
    print math.sqrt(var)

### FIXED CODE ###

import math
while True:
    n=input()
    if n==0: break
    s=map(int,raw_input().split())
    mean=float(sum(s))/len(s)
    var=[(x-mean)**2/n for x in s]
    print math.sqrt(sum(var))
def a(s,i):
    if i = l-1:
        if eval(s)==7:
            return s+"=7"
        return
    a(s+"+"+N[i],i+1)
    a(s+"-"+N[i],i+1)

N = input()
l = len(N)


print(a(N[0],0)

### FIXED CODE ###

def dfs(i, Str, res):
    if i==3:
        if res==7:
            print(Str+"=7")
            exit()
        return
    
    dfs(i+1,Str+"+"+s[i+1],res+int(s[i+1]))
    dfs(i+1,Str+"-"+s[i+1],res-int(s[i+1]))

s=input()
dfs(0,s[0],int(s[0]))
dp = [Yes] #i円の買い物ができるか
for i in range(99):
  dp.append(No)
for i in range(100, x+1):
  if(i < 106):
    dp.append(Yes)
  else:
    if((dp[i-100] == Yes) or (dp[i-101] == Yes) or (dp[i-102] == Yes) or (dp[i-103] == Yes) or (dp[i-104] == Yes) or (dp[i-105] == Yes)):
      dp[i].append(Yes)
    else:
      dp[i].append(No)
print(dp[x])

### FIXED CODE ###

dp = [True] #i円の買い物ができるか
x = int(input())
for i in range(99):
  dp.append(False)
for i in range(100, x+1):
  if(i < 106):
    dp.append(True)
  else:
    if(dp[i-100] or dp[i-101] or dp[i-102] or dp[i-103] or dp[i-104] or dp[i-105]):
      dp.append(True)
    else:
      dp.append(False)
if(dp[x]):
  print(1)
else:
  print(0)
g=lambda a,b:abs(a[0]*b[1]-a[1]*b[0])

while True:
    t=input()
    if t=="":break
    l=[float(i) for i in t.split()]
    ba=[l[0]-l[2],l[1]-l[3]]
    ab=[-i for i in ba]
    cb=[l[2]-l[4],l[3]-l[5]]
    bc=[-i for i in cb]
    ca=[l[0]-l[4],l[1]-l[5]]
    ac=[-i for i in ca]
    ap=[l[6]-l[0],l[7]-l[1]]
    bp=[l[6]-l[2],l[7]-l[3]]
    cp=[l[6]-l[4],l[7]-l[5]]
    if g(ab,ac)<g(ab,ap) or g(ba,bc)<g(ba,bp) or g(ca,cb)<g(ca,cp):
        print("NO")
    else:
        print("YES")


### FIXED CODE ###

g=lambda a,b,c:(a[0]-b[0])*(b[1]-c[1])-(b[0]-c[0])*(a[1]-b[1])

while True:
    try:t=input()
    except:break
    l=[float(i) for i in t.split()]
    b=[g(l[0:2],l[2:4],l[6:8]),g(l[2:4],l[4:6],l[6:8]),g(l[4:6],l[0:2],l[6:8])]
    if len([i for i in b if i>0])==3 or len([i for i in b if i<0])==3:
        print("YES")
    else:
        print("NO")
n, m = map(int,(input().split()))
d = {}
for i in range(n):
    a, b = map(int,(input().split()))
    d[a]=b
d = sorted(d.items())
ans = 0
for i in range(n):
    if d[i][1] >= m:
        ans += d[i][0]*m
        break
    else:
        ans += d[i][0]*d[i][1]
        m -= d[i][1]
print(ans)

### FIXED CODE ###

n, m = map(int,(input().split()))
d = []
for i in range(n):
    a, b = map(int,(input().split()))
    d.append([a,b])
d = sorted(d)
ans = 0
for i in range(n):
    if d[i][1] >= m: # 残り本数 >= この値段の本数
        ans += d[i][0]*m
        break
    else:
        ans += d[i][0]*d[i][1]
        m -= d[i][1]
        if m <= 0:
            break
print(ans)
N,M = (int(i) for i in input().split())
a = [int(input()) for i in range(M)]
hoge = [0] * N
if 1 not in a:
    hoge[0] = 1
if 2 not in a:
    hoge[1] = hoge[0] + 1

for i in range(2,N):
    if i + 1 in a:
        hoge[i] = 0
    elif i in a and (i-1) in a:
        hoge[i] = 0
    elif i in a:
        hoge[i] = hoge[i - 2]
    elif (i-1) in a:
        hoge[i] = hoge[i - 1]
    else:
        hoge[i] = hoge[i-1] + hoge[i-2]
        hoge[i] = hoge[i] % (10**9 + 7)
print(hoge[N-1] % (10**9 + 7))




### FIXED CODE ###

N, M = map(int, input().split())
A = set(int(input()) for _ in range(M))
mod = 10 ** 9 + 7

dp = [0] * (N+1)
dp[0] = 1
for i in range(1, N+1):
    if i in A:
        continue
    if i == 1:
        dp[i] = 1
        continue
    dp[i] = dp[i-1] + dp[i-2]

print(dp[N] % mod)
while True:
    a,b=map(int,input().sprit())
    if (a==0 and b==0):
        break
    if a>b:
        swap=a
        a=b
        b=swap
        
    print('%d %d'%(a,b))




### FIXED CODE ###

while True:
    a,b=map(int,input().split())
    if (a==0 and b==0):
        break
    if a>b:
        swap=a
        a=b
        b=swap       
    print('%d %d'%(a,b))
import itertools

N = int(input())
params = []
for i in range(N):
    xyh = [int(n) for n in input().split()]
    params.append(xyh)

if len(params) == 1:
    print(*params[0])

else:

    #Cx, Cy, H = 0, 0, 0
    for cxi, cyi in itertools.product(range(101), range(101)):
        hight_ = params[0][2] + abs(params[0][0] - cxi) + abs(params[0][1] - cyi)

        #counter = 0
        for k in range(1, N):
            if params[k][2] > 0:
                hight = params[k][2] + abs(params[k][0] - cxi) + abs(params[k][1] - cyi)
                #if counter == 0:
                #    hight_ = hight
                #counter += 1

                if hight < 1:
                    break
                else:
                    if hight != hight_:
                        break
                    else:
                        hight_ = hight
            elif params[k][2] == 0:
                if 1 > (abs(params[k][0] - cxi) + abs(params[k][1] - cyi)):
                    break

        else:
            Cx = cxi
            Cy = cyi
            H = hight
        continue

    print(Cx, Cy, H)

### FIXED CODE ###

N = int(input())
params = []
for i in range(N):
    xyh = [int(n) for n in input().split()]
    params.append(xyh)

for cxi in range(101):
    for cyi in range(101):
        for k in range(N):
            if params[k][2] > 0:
                hight = params[k][2] + abs(params[k][0] - cxi) + abs(params[k][1] - cyi)

        for k in range(N):
            if params[k][2] != max((hight - abs(params[k][0] - cxi) - abs(params[k][1] - cyi)), 0):
                break
        
        else:
            print(cxi, cyi, hight)
n=int(input())
a=[]
for i in range(n):
    a.append(input())
flag=0
for i in range(n):
    s=a[i]
    
   if i==0:
       continue
   else:
       if last!=a[i][len(a[i])-1]:
           flag=1
           
   last=a[i][len(a[i])-1]
if flag==1:
    print("No")
else:
    print("Yes")


### FIXED CODE ###

a,b=map(int,input().split())
flag=0
for i in range(1,4):
    if a*b*i%2==1:
        flag=1
if flag==1:
    print("Yes")
else:
    print("No")
n,m = map(int,input().split())
f = [False for _ in range(n)]
a = [[] for _ in range(n)]

def dfs(k):
    f[k] = True
    for g in a[k]:
        if not f[g]:
            dfs(g)

def main():
    res = 0
    for _ in range(m):
        x,y,z = map(int,input().split())
        a[x-1].append(y-1)
        a[y-1].append(x-1)
    for i in range(n):
        if not f[i]:
            res += 1
            dfs(i)
    print(res)

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
n,m = map(int,input().split())
f = [False for _ in range(n)]
a = [[] for _ in range(n)]
res = 0

def dfs(k):
    f[k] = True
    for g in a[k]:
        if not f[g]:
            dfs(g)

for _ in range(m):
    x,y,z = map(int,input().split())
    a[x-1].append(y-1)
    a[y-1].append(x-1)

for i in range(n):
    if not f[i]:
        res += 1
        dfs(i)
print(res)
def f(i,ans,l,t):
  if (i+1) == (len(l)-1):
    if (ans+l[i]) > l[i+1]:
      ans = ans + l[i]-l[i+1]
      return t+ans
    else:
      return t
  else:
    if (ans+l[i]) > l[i+1]:
      ans = ans + l[i]-l[i+1]
      return f(i+1,ans,l,t+ans)
    else:
      return f(i+1,0,l,t)
n = input("")
an = input("").split(" ")
ani = [int(a) for a in an]
if len(ani) == 1:
  print("0")
else:
  print(str(f(0,0,ani,0)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(2000000)
def f(i,ans,l,t):
  if (i+1) == (len(l)-1):
    if (ans+l[i]) > l[i+1]:
      ans = ans + l[i]-l[i+1]
      return t+ans
    else:
      return t
  else:
    if (ans+l[i]) > l[i+1]:
      ans = ans + l[i]-l[i+1]
      return f(i+1,ans,l,t+ans)
    else:
      return f(i+1,0,l,t)
n = input("")
an = input("").split(" ")
ani = [int(a) for a in an]
if len(ani) == 1:
  print("0")
else:
  print(str(f(0,0,ani,0)))
def bfs(graph, start, goal, connection):
    visited = {start: None}
    unvisited = [start]
    while unvisited:
        now = unvisited[0]
        if now == goal or (1000000*now + goal) in connection:
            connection[1000000*start + goal] = 1
            connection[1000000*goal + start] = 1
            return "yes"
        unvisited = unvisited[1:]
        for next in graph[now]:
            if not (next in visited):
                unvisited.append(next)
                visited[next] = now
    return "no"

n, m = map(int, input().split())
g = [[] for i in range(n)]
c = {}

for i in range(m):
    inp = list(map(int, input().split()))
    g[inp[0]].append(inp[1])
    g[inp[1]].append(inp[0])
    connection[1000000*inp[0] + inp[1]] = 1
    connection[1000000*inp[1] + inp[0]] = 1

q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    print(bfs(g, s, t, c))

### FIXED CODE ###

from collections import deque

def bfs(graph, start):
    visited = {start: None}
    unvisited = deque()
    unvisited.append(start)
    while unvisited:
        now = unvisited.popleft()
        for next in graph[now]:
            if not (next in visited):
                unvisited.append(next)
                visited[next] = now
    return visited

n, m = map(int, input().split())
g = [set() for i in range(n)]
group = []

for i in range(m):
    a, b = map(int, input().split())
    g[a].add(b)
    g[b].add(a)

q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    for j in range(len(group)):
        if s in group[j] and t in group[j]:
            print("yes")
            break
        elif s in group[j]:
            print("no")
            break
    else:
        group_tmp = set(bfs(g, s).keys())
        if t in group_tmp:
            print("yes")
        else:
            print("no")
        group.append(group_tmp)
import math

# input
X = int(input())

ans = 1

for b in range(2, math.sqrt(X)):
    p = 1
    while b ** p <= X:
        if b ** p > ans:
            ans = b ** p
        p += 1

### FIXED CODE ###

import math

# input
X = int(input())

ans = 1

for b in range(2, 32):
    p = 2
    while b ** p <= X:
        if b ** p > ans:
            ans = b ** p
        p += 1

print (ans)
import functools

def gcd(a,b):
    while b > 0:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    return a * b / gcd(a, b)

N = int(input())
a = list(map(int, input().split()))
assert(len(a) == N)

lcmVal = int(functools.reduce(lcm, a))
print(sum(map(lambda x: (lcmVal-1) % x, a)))


### FIXED CODE ###

import functools

def gcd(a,b):
    while b > 0:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    return a * b / gcd(a, b)

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

lcmVal = int(functools.reduce(lcm, a, 0))
print(sum(map(lambda x: (lcmVal-1) % x, a)))
N = int(input())
a = [int(i) for i in input().split()]
print(sum([min(a[l:r + 1]) for l in range(N) for r in range(l, N)]))

### FIXED CODE ###

string = input()
stack = []
for s in string:
    if s == "T" and stack and stack[-1] == "S":
        stack.pop()
    else:
        stack.append(s)
print(len("".join(stack)))
n = int(input())
count=0
for i in range(0,n):
    t,x,y = map(int, input().split())
    if (t-temp)>=x+y and (x+y-(t-temp))%2==0:
        count=count+1
    temp=t
if count==n:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n = int(input())
count=0
temp=0
xtemp=0
ytemp=0
for i in range(0,n):
    t,x,y = map(int, input().split())
    if abs(t-temp)>=abs(x-xtemp)+abs(y-ytemp) and (x-xtemp+y-ytemp-(t-temp))%2==0:
        count=count+1
    temp=t
    xtemp=x
    ytemp=y
if count==n:
    print("Yes")
else:
    print("No")
N, M = map(int,input().split())
li = list(map(int, input().split()))

c = sum(li) / 4*M
res = 0
for l in li:
    res += 1 if l >= c
if res == M:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

N, M = map(int,input().split())
li = list(map(int, input().split()))

c = sum(li) / (4*M)
res = 0
for l in li:
    if l >= c:
        res += 1
if res >= M:
    print('Yes')
else:
    print('No')
import heapq
from collections import defaultdict, deque
from math import ceil, factorial

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))

N, M = mii()
edge = defaultdict(list)
memo = defaultdict(int)
done = defaultdict(bool)


def dp(v):
    if done[v]:
        return memo[v]
    ret = 0
    for to in edge[v]:
        ret = max(ret, dp(to) + 1)
    done[v] = True
    memo[v] = ret
    return ret


for i in range(M):
    x, y = mii()
    edge[x].append(y)
ans = 0
for v in range(1, N+1):
    ans = max(ans, dp(v))

print(ans)

### FIXED CODE ###

import heapq
from collections import defaultdict, deque
from math import ceil, factorial
import sys
sys.setrecursionlimit(10**7)

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))
# ---
N, M = mii()
edge = defaultdict(list)
memo = defaultdict(int)
done = defaultdict(bool)


def dp(v):
    if done[v]:
        return memo[v]
    ret = 0
    for to in edge[v]:
        ret = max(ret, dp(to) + 1)
    done[v] = True
    memo[v] = ret
    return ret


for i in range(M):
    x, y = mii()
    edge[x].append(y)
ans = 0
for v in range(1, N+1):
    ans = max(ans, dp(v))

print(ans)
rgb = int(''.join(input()))
if rgb % 4 == 0:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

r, g, b = map(int, input().split())
if (r*100 + g*10 + b) % 4 == 0:
    print('YES')
else:
    print('NO')
n=int(input())
p=[int(x) for x in input().split()]
pp=[int(x+1) for x in range(n)]

count=0

for i in range(n):
    if p[i]!=pp[i]:
        count+=1

if count <= 2
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n=int(input())
p=[int(x) for x in input().split()]
pp=[int(x+1) for x in range(n)]

count=0

for i in range(n):
    if p[i]!=pp[i]:
        count+=1

if count <= 2:
    print("YES")
else:
    print("NO")
n, k = map(int, input().split())
a = list(map(int, input().split()))
a1 = []
if max(a) < k:
    print("IMPOSSIBLE")
    exit()

for i in range(1, n):
    a1.append(abs(a[i-1]-a[i]))
a1 = sorted(a1)

for i in range(1, n-1):
    if a1[i] % a1[0] != 0:
        print("POSSIBLE")
        break
else:
    if k % a1[0] == 0 or a1[0] == 1:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

### FIXED CODE ###

from math import gcd
n, k = map(int, input().split())
a = list(map(int, input().split()))
if max(a) < k:
    print("IMPOSSIBLE")
    exit()
if k in a:
    print("POSSIBLE")
    exit()
a_gcd = a[0]
for i in range(1, n):
    a_gcd = gcd(a_gcd, a[i])

if k % a_gcd == 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
K, X = map(int, input().split())
 for i in range(X - K + 1, X + K):
  if i < X + K - 1:
    print(i, end=' ')
  else:
    print(i)


### FIXED CODE ###

a, b = map(int, input().split())
print(max([a+b,a-b,a*b]))
x=int (input())

i=0

while(x>=100((1+0.01)**i){
  i=i+1
}


print(i)

### FIXED CODE ###

X=int(input())
total,Y=100,0
while X>total:
  total=total*101//100
  Y=Y+1
print(Y)
import sys
import numpy as np
input = lambda: sys.stdin.readline().rstrip()

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a = sorted([i for i in a if a.count(i) == 1])
    a = np.array(a)
    ans = []
    if let(set(a)) == 1:
        print(0)
        return
    while a != []:
        ans.append(a[0])
        a = a[a%a[0] != 0]
    print(len(ans)+1)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import collections
input = lambda: sys.stdin.readline().rstrip()

def main():
    n = int(input())
    a = sorted([int(i) for i in input().split()])
    cnt_list = collections.Counter(a)
    search_list = [0] * (a[-1]+1)
    ans = 0
    for num, cnt in cnt_list.items():
        search_list[num] = cnt
    for i in a:
        if search_list[i] == 1:
            ans += 1
        for j in range(i, a[-1]+1, i):
            search_list[j] = 0
    print(ans)
    
if __name__ == '__main__':
    main()
N=int(input())
if N==1:
    print("Hello World")
else:
    a,b=map(int,input().split())
    print(a+b)

### FIXED CODE ###

N=int(input())
if N==1:
    print("Hello World")
else:
    a=int(input())
    b=int(input())
    print(a+b)
k = int(input())
table = [1,2,3,4,5,6,7,8,9,10,11,12,21,22,23,32,33,34,43,44,45,54,55,56,65,66,67,76,77,78,87,88,89,98]
key1, key2,key3 = 0,0,0
for i in range(1,9):
    key1=int(str(i)+str(i-1)+str(i-1))
    key2=int(str(i)+str(i)+str(i))
    key3=int(str(i)+str(i+1)+str(i+1))
    table.append(key1-1)
    table.append(key1)
    table.append(key1+1)
    table.append(key2-1)
    table.append(key2)
    table.append(key2+1)
    table.append(key3-1)
    table.append(key3)
    table.append(key3+1)
table.pop()
table.append(987)
table.append(988)
table.append(989)
table.append(998)
table.append(999)
table.append(1000)
table.append(1001)
table.append(1010)
table.append(1011)
table.append(1012)
table.append(1100)
table.append(1101)
table.append(1110)
table.append(1111)
table.append(1112)
table.append(1121)
table.append(1122)
table.append(1123)
table.append(1210)
table.append(1211)
table.append(1212)
table.append(1221)
table.append(1222)
table.append(1223)
table.append(1232)
table.append(1233)
table.append(1234)
for j in range(2,9):
        key1=int(str(j)+str(j-1)+str(j-1)+str(j-1))
        key2=int(str(j)+str(j)+str(j)+str(j))
        key3=int(str(j)+str(j+1)+str(j+1)+str(j+1))    
    table.append(key1-1)
    table.append(key1)
    table.append(key1+1)
    table.append(key2-1)
    table.append(key2)
    table.append(key2+1)
    table.append(key3-1)
    table.append(key3)
    table.append(key3+1)
table.pop()
table.append(9887)
table.append(9888)
table.append(9889)
table.append(9998)
table.append(9999)
print(table[k-1])

### FIXED CODE ###

k = int(input())
lunlun = []
def dfs(A):
    if len(A) == 10:
        return
    else:
        start = int(A[-1])
        if start == 9:
            for i in range(start-1, start+1):
                A.append(str(i))
                lunlun.append("".join(A))
                dfs(A)
                A.pop()
        elif start == 0:
            for i in range(start, start+2):
                A.append(str(i))
                lunlun.append("".join(A))
                dfs(A)
                A.pop()
        else:
            for i in range(start-1, start+2):
                A.append(str(i))
                lunlun.append("".join(A))
                dfs(A)
                A.pop()
for j in range(1, 10):
    lunlun.append(str(j))
    dfs([str(j)])
lunlun = list(map(int, lunlun))
lunlun.sort()
print(lunlun[k-1])
x, y = map(int, input().split())

for a in range(x + 1):
    if  a == - y / 2 + x:
        print('Yes')
        exit(1)

print('No')


### FIXED CODE ###

x, y = map(int, input().split())

for a in range(x + 1):
    tem = 2 * a + 4 * (x - a)
    if (tem == y):
        #  and (2 * x <= y <= 4 * x):
        print('Yes')
        exit()

print('No')
A,B,N=map(int, input().split())
ans=[]
for i in range(1,N+1,B//A):
    ans.append(int(A*i/B)-A*int(i/B))
print(max(ans))

### FIXED CODE ###

A,B,N=map(int, input().split())
if N>=B-1:
    print(int(A*(B-1)/B)-A*int((B-1)/B))
else:
    print(int(A*N/B)-A*int(N/B))