Harryxun/stf_run huggingface dataset:
N,M=map(int,input().split())
from collections import defaultdict
branch=defaultdict(set)
for i in range(M):
    a,b=map(int,input().split())
    branch[a]|={b}
    branch[b]|={a}
jisuu=[len(branch[i]) for i in range(N+1)]
if jisuu.count(1)>=2:
    start=jisuu.index(1)
    visited={start}
    check=[[start]]
    while len(check)>0:
        c=check.pop()
        now=c[-1]
        for nex in branch[now]:
            if nex not in visited:
                if jisuu[nex]==1:
                    path=c+[nex]
                    check=[]
                    break
                else:
                    check+=[c+[nex]]
                    visited|={nex}
else:
    for i in range(1,1+N):
        if jisuu[i]==2:
            a,b=list(branch[i])
            if jisuu[a]==2:
                start=i
                goal=a
                nex=b
                break
            elif jisuu[b]==2:
                start=i
                goal=b
                nex=a
                break
    visited={start,nex}
    check=[[start,nex]]
    while len(check)>0:
        c=check.pop()
        now=c[-1]
        for nex in  branch[now]:
            if nex not in visited:
                if nex==goal:
                    path=c+[nex]
                    check=[]
                    break
                else:
                    check+=[c+[nex]]
                    visited|={nex}
print(len(path))
print(" ".join(map(str,path)))

### FIXED CODE ###

N,M=map(int,input().split())
from collections import deque,defaultdict
branch=defaultdict(set)
for i in range(M):
    a,b=map(int,input().split())
    branch[a-1]|={b-1}
    branch[b-1]|={a-1}
path=deque([0])
for x in branch[0]:
    path.append(x)
    break
used=set(path)
while True:
    A,B=False,False
    if len(branch[path[0]]-used)==0:
        A=True
    else:
        for x in branch[path[0]]:
            if x in used:
                continue
            path.appendleft(x)
            used|={x}
            break
    if len(branch[path[-1]]-used)==0:
        B=True
    else:
        for x in branch[path[-1]]:
            if x in used:
                continue
            path.append(x)
            used|={x}
            break
    if A and B:
        break
path=[p+1 for p in path]
print(len(path))
print(" ".join(map(str,path)))
import math
n, k = map(int, input().split())
a = input()
print(math.celi(n-1/k-1))

### FIXED CODE ###

import math
n, k = map(int, input().split())
a = input()
print(math.ceil((n-1)/(k-1)))
import numpy as np
a=[[[],[],[]],[[],[],[]]]
for i in range(int(input())):
    s,t,u=map(str,input().split())
    if u=="R":
        a[0][0].append(int(s))
        a[1][1].append(int(t))
    elif u=="L":
        a[0][2].append(int(s))
        a[1][1].append(int(t))
    elif u=="U":
        a[1][0].append(int(t))
        a[0][1].append(int(s))
    else:
        a[1][2].append(int(t))
        a[0][1].append(int(s))
for i in range(3):
    a[0][i]=[min(a[0][i]+[INF]),max(a[0][i]+[-INF])]
    a[1][i]=[min(a[1][i]+[INF]),max(a[1][i]+[-INF])]
l=10**8+1
r=0
while l-r>5*(10**-6:
    x2=(l*2+r)/3
    x1=(l+r*2)/3
    h=max(a[0][0][1]+x2,a[0][1]+x2,a[0][
    i=
    j=
    k=
    s=
    t=
    u=
    v=
    print(s,t,u,v)
    if (max(s)-min(s))*(max(t)-min(t))<=(max(u)-min(u))*(max(v)-min(v)):
        r=x1
    else:
        l=x2
print((max(s)-min(s))*(max(t)-min(t)))

### FIXED CODE ###

x,a=map(int,input().split());print(0 if x<a else 10)
n = int(input())
d = list(map(int,input().split()))
d.sort()
ans = 0
if n % 2 = 1:
  print(ans)
else:
  ans = d[(n - 1)/2 + 1] - d[(n - 1)/2]
  print(ans)


### FIXED CODE ###

n = int(input())
d = list(map(int,input().split()))
d.sort()
ans = 0
if n % 2 == 1:
  print(ans)
else:
  ans = d[(n // 2)] - d[(n // 2 - 1)]
  print(ans)
import math

inp = input()

m = [x.split() for x in inp]

count = 0

for i in inp:
    x, y = i.split()

    xx = x ** 2
    yy = y ** 2

    ans = math.sqrt(xx + yy)

    if ans >= y:
        count += 1

print(count)

### FIXED CODE ###

import math

N, D = map(int, input().split())
count = 0
for _ in range(N):
    x, y = map(int, input().split())
    xx = x ** 2
    yy = y ** 2

    ans = math.sqrt(xx + yy)
    if ans <= D:
        count += 1

print(count)
input(a)
if(a%2==1)
	i=(a+1)/2
	j=(a-1)/2
else 
	i=a/2
	j=a/2
print(i+j)

### FIXED CODE ###

a=int(input())
if a%2==0:
  ans=int((a/2)**2)
else:
  ans=int(((a-1)/2)*((a+1)/2))
print(ans)
import sys
a,b=map(int,input().split())
if b==1:
  print("0")
  sus.exit()
p=1
ans=0
for i in range(0,20):
  p+=a-1
  ans+=1
  if p>=b:
    print(ans)
    sys.exit()

### FIXED CODE ###

import sys
a,b=map(int,input().split())
if b==1:
  print("0")
  sys.exit()
p=1
ans=0
for i in range(0,20):
  p+=a-1
  ans+=1
  if p>=b:
    print(ans)
    sys.exit()
if(S == ABC):
	print("ARC")
elif(S == ARC):
	print("ABC")



### FIXED CODE ###

S = input()

if(S == "ABC"):
	print("ARC")
elif(S == "ARC"):
	print("ABC")
n,m=map(int, input().split())  #複数数値入力

import sys

sys.setrecursionlimit(10**20)

if m == 0:
    print(countWays_memo(n))
else:
    list_a = []
    for i in range(m):
        list_a.append(int(input()))

    def countWays_memo(n):
        memo = [-1]*(n+1)
        def _countWays(n):
            if n < 0:
                return 0
            elif n == 0:
                return 1
            else:
                if memo[n] > -1:
                    return memo[n]
                else:
                    memo[n] = _countWays(n-1) + _countWays(n-2) 
                    return memo[n]
        return _countWays(n)

    steps = [list_a[0]]
    now_step=list_a[0]+1
    for i in range(len(list_a)-1):
        steps.append(list_a[i+1]-now_step)
        now_step = list_a[i+1]+1
    steps.append(n-now_step+1)


    dict_steps = {}
    for s in set(steps):
        dict_steps[s] = steps.count(s)

    ans = 1
    for k,v in dict_steps.items():
        ans *= countWays_memo(k-1)**v

    print(ans% 1000000007)

### FIXED CODE ###

n,m=map(int, input().split())  #複数数値入力

import sys

sys.setrecursionlimit(10**9)

def countWays_memo(n):
    memo = [-1]*(n+1)
    def _countWays(n):
        if n < 0:
            return 0
        elif n == 0:
            return 1
        else:
            if memo[n] > -1:
                return memo[n]
            else:
                memo[n] = _countWays(n-1) + _countWays(n-2) 
                return memo[n]
    return _countWays(n)
    
if m == 0:
    print(countWays_memo(n)% 1000000007)
else:
    list_a = []
    for i in range(m):
        list_a.append(int(input()))

    steps = [list_a[0]]
    now_step=list_a[0]+1
    for i in range(len(list_a)-1):
        steps.append(list_a[i+1]-now_step)
        now_step = list_a[i+1]+1
    steps.append(n-now_step+1)


    dict_steps = {}
    for s in set(steps):
        dict_steps[s] = steps.count(s)

    ans = 1
    for k,v in dict_steps.items():
        ans *= countWays_memo(k-1)**v

    print(ans% 1000000007)
N = int(input())
Y = list(str(N))
Z =[]
for i in Y:
    Z.append(int(i))
K = int(input())
m = len(str(N))
def nn(Z,K,m):
    ans = 0
    if K == 1:
        y = Z[0]
        ans += (m-1) * 9 + y
        #print(ans)
    elif K == 2:
        #0 
        ans += ((m-1) * (m-2) // 2) * 9 * 9
        #print(ans)
        #mid
        ans += (Z[0]-1) * (m-1) * 9
        #print(ans)
        #max
        K -= 1
        m -= 1
        Z = Z[1:]
        ans += nn(Z,K,m)
        #print(ans)
    elif K == 3:
        #0 
        ans += ((m-1) * (m-2) * (m-3) // 6) * 9 * 9 * 9
        #print(ans)
        #mid
        ans += (Z[0]-1) * ((m-1) * (m-2) // 2) * 9 * 9
        #print(ans)
        #max
        K -= 1
        m -= 1
        Z = Z[1:]
        ans += nn(Z,K,m)
    return ans
ans = nn(Z,K,m)        
print(ans)

### FIXED CODE ###

N = int(input())
Y = list(str(N))
Z =[]
for i in Y:
    Z.append(int(i))
K = int(input())
m = len(str(N))
def nn(Z,K,m):
    ans = 0
    if m < K:
        return ans
    else:
        if K == 1:
            y = Z[0]
            ans += (m-1) * 9 + y
            #print(ans)
        elif K == 2:
            #0 
            ans += ((m-1) * (m-2) // 2) * 9 * 9
            #print(ans)
            #mid
            ans += (max(0,Z[0]-1)) * (m-1) * 9
            #print(ans)
            #max
            K -= 1
            m -= 1
            Z = Z[1:]
            for _ in range(100):
                if Z[0] == 0:
                    m -= 1
                    Z = Z[1:]   
                else:
                    break
                if len(Z) == 0:
                    break            
            ans += nn(Z,K,m)
            #print(ans)
        elif K == 3:
            #0 
            ans += ((m-1) * (m-2) * (m-3) // 6) * 9 * 9 * 9
            #print(ans)
            #mid
            ans += (max(0,Z[0]-1)) * ((m-1) * (m-2) // 2) * 9 * 9
            #print(ans)
            #max
            K -= 1
            m -= 1
            Z = Z[1:]
            for _ in range(100):
                if Z[0] == 0:
                    m -= 1
                    Z = Z[1:]   
                else:
                    break
                if len(Z) == 0:
                    break
            ans += nn(Z,K,m)
        return ans
if len(str(N)) < K:
    ans = 0
else:
    ans = nn(Z,K,m)        
print(ans)
N = int(input())
A = list(map(int, input().split()))

A = sorted(A)

count_m = 0
count_z = 0
count_p = 0
sum_abs = 0

for i in range(N):
    if A[i] < 0:
        count_m += 1
        sum_abs -= A[i]
    elif A[i] == 0:
        count_z += 1
    else:
        count_p += 1
        sum_abs += A[i]

if count_m + count_z == 0:
    print(sum_abs-2*min(A))
    tmp = A[0]
    for i in range(N-2):
        print(tmp, A[i+1])
        tmp -= A[i+1]
    

elif count_p + count_z == 0:
    print(sum_abs+2*max(A))
    tmp = A[-1]
    for i in range(N-1):
        print(tmp, A[i])
        tmp -= A[i]

elif count_p + count_m == 0:
    print(0)
    for i in range(N-1):
        print(0, 0)

else:
    print(A[2*N])
    print(sum_abs)
    cmz = count_m + count_z
    tmp = A[-1]
    for i in range(cmz - 1):
        print(tmp, A[i])
        tmp -= A[i]
    tmp_2 = A[cmz-1]
    for i in range(count_p-1):
        print(tmp_2, A[i+cmz])
        tmp_2 -= A[i+cmz]
    print(tmp, tmp_2)

### FIXED CODE ###

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

A = sorted(A)

count_m = 0
count_z = 0
count_p = 0
sum_abs = 0

for i in range(N):
    if A[i] < 0:
        count_m += 1
        sum_abs -= A[i]
    elif A[i] == 0:
        count_z += 1
    else:
        count_p += 1
        sum_abs += A[i]

if count_m + count_z == 0:
    print(sum_abs-2*min(A))
    tmp = A[0]
    for i in range(N-2):
        print(tmp, A[i+1])
        tmp -= A[i+1]
    print(A[-1], tmp)

elif count_p + count_z == 0:
    print(sum_abs+2*max(A))
    tmp = A[-1]
    for i in range(N-1):
        print(tmp, A[i])
        tmp -= A[i]

elif count_p + count_m == 0:
    print(0)
    for i in range(N-1):
        print(0, 0)

else:
    print(sum_abs)
    cmz = count_m + count_z
    tmp = A[-1]
    for i in range(cmz - 1):
        print(tmp, A[i])
        tmp -= A[i]
    tmp_2 = A[cmz-1]
    if count_p != 0:
        for i in range(count_p-1):
            print(tmp_2, A[i+cmz])
            tmp_2 -= A[i+cmz]
        print(tmp, tmp_2)
n=int(input())
a=n%100
b=a%10
if b==3:
  print("bon")
if b==2 || b==4 || b==5 || b==7 || b==9:
  print("hon")
if b==0 || b==1 || b==6 || b==8:
  print ("pon")

### FIXED CODE ###

n=int(input())
a=n%100
b=a%10
if b==3:
  print("bon")
if b==2 or b==4 or b==5 or b==7 or b==9:
  print("hon")
if b==0 or b==1 or b==6 or b==8:
  print ("pon")
5 1000000000

### FIXED CODE ###

import math
import fractions
from functools import reduce

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

n,m = (int(x) for x in input().split())
a = list(map(int, input().split()))

lc = int(lcm_list(a) // 2)

tmp = 0
bol = 0
num = a[0]
while num % 2 == 0:
        num = num // 2
        tmp += 1
cnt = 0
for num in a:
    cnt = 0
    while num % 2 == 0:
        num = num // 2
        cnt += 1
    if cnt != tmp:
        bol = 1

if lc > m: print(0)
elif bol == 1: print(0)
else: print(int(((m / lc) + 1) // 2))
x = input()
if(x >= 30):
  print('Yes')
  else:
        print('No')

### FIXED CODE ###

x = int(input())
if x >= 30:
  print('Yes')
else:
  print('No')
import sys
sys.setrecursionlimit(10**9)
def solve(n, m, q, A):
  if len(A) == m+1:
    print(A)
    rtn = 0
    for a, b, c, d in q:
      rtn += d if A[b]-A[a] == c else 0
    return rtn
  else:
    return max([solve(n, m, q, A+[i]) for i in range(A[-1], m+1)])

N, M, Q = map(int, input().split())
ABCD = [list(map(int, input().split())) for _ in range(Q)]
print(solve(N, M, ABCD, [1]))

### FIXED CODE ###

from collections import deque
N, M, Q = map(int, input().split())
ABCD = [list(map(int, input().split())) for _ in range(Q)]
ans = 0
q = deque()
q.append([1])
while q:
  A = q.pop()
  if len(A) == N+1:
    ans = max(ans, sum([d if A[b]-A[a] == c else 0 for a, b, c, d in ABCD]))
  else:
    for i in range(A[-1], M+1):
      q.append(A+[i])
print(ans)
N,A,B = map(int,input().split())
if A ==0 :
    print(0)
elif B==0:
    print(N)
else:
    m = N % (A+B)
    n = N // (A+B)
    ans = A * n
    if m > A:
        print(ans+A)n
    else:
        print(ans+m)


### FIXED CODE ###

N,A,B = map(int,input().split())
if A ==0 :
    print(0)
elif B==0:
    print(N)
else:
    m = N % (A+B)
    n = N // (A+B)
    ans = A * n
    if m > A:
        print(ans+A)
    else:
        print(ans+m)
L, R = map(int, input().split())
ans_l = []
for i in range(L,R):
    for j in range(i+1,R+1):
        ans = (i*j)%2019
        if ans !=0:
            ans_l.append(ans)
        else:
            ans_l.append(0)
            break;
print(min(ans))

### FIXED CODE ###

L, R = map(int, input().split())
ans_l = []
if R-L<2019:
    for i in range(L,R):
        for j in range(i+1,R+1):
            ans = (i*j)%2019
            ans_l.append(ans)
    print(min(ans_l))
else:
    print(0)
import sys
sys.setrecursionlimit(10 ** 9)
lst = [[1,2], [2, 5], [3, 5], [4, 4], [5, 5], [6, 6], [7, 3], [8, 7], [9, 6]]
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse = True)
# print (A)

def num(k):
    return lst[k-1][1]

# for i in A:
    # print (num(i), end = ', ')
# print ()

INF = 10 ** 9
dp_lst = [-INF] * (N + 1)
dp_lst[0] = 0
def dp(i):
    if dp_lst[i] != -INF:
        return dp_lst[i]
    tmp = -INF
    for j in A:
        if i >= num(j):
            tmp = max(tmp, dp(i - num(j)) + 1)
    dp_lst[i] = tmp
    return dp_lst[i]

a = dp(N)
# print (a)
# print (dp_lst)   
# print ([0] * 10 +[i+1 for i in range(20)])

# print (len(str(71111111111111111111111111111111111111111111111111)))

def check(A):
    if dp_lst[N-num(A)] == dp_lst[N] - 1:
        return True
    else:
        return False

# print (a)
while a > 0:
    for i in A:
        if check(i):
            print (i, end = '')
            N -= num(i)
            a -= 1
            break
        else:
            pass
            # print ('B')
print ()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5)
lst = [[1,2], [2, 5], [3, 5], [4, 4], [5, 5], [6, 6], [7, 3], [8, 7], [9, 6]]
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse = True)
# print (A)

def num(k):
    return lst[k-1][1]

# for i in A:
    # print (num(i), end = ', ')
# print ()

INF = 10 ** 5
dp_lst = [-INF] * (N + 1)
dp_lst[0] = 0
def dp(i):
    if dp_lst[i] != -INF:
        return dp_lst[i]
    tmp = -INF
    for j in A:
        if i >= num(j):
            tmp = max(tmp, dp(i - num(j)) + 1)
    dp_lst[i] = tmp
    return dp_lst[i]

a = dp(N)
# print (a)
# print (dp_lst)   
# print ([0] * 10 +[i+1 for i in range(20)])

# print (len(str(71111111111111111111111111111111111111111111111111)))

def check(A):
    if N - num(A) < 0:
        return False
    if dp_lst[N-num(A)] == dp_lst[N] - 1:
        return True
    else:
        return False

# print (a)
while a > 0:
    for i in A:
        if check(i):
            print (i, end = '')
            N -= num(i)
            a -= 1
            break
        else:
            pass
            # print ('B')
print ()
N = int(input())
v = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    v[a].append([b,i])

ans = [None] * (N-1)

def decide_colord(cur,color):
    cnt = 1
    for (to,j)in v[cur]:
        if cnt == color:
            cnt += 1
        ans[j] = cnt
        decide_colord(to,cnt)
        cnt += 1
decide_colord(0,0)
print(max(ans))
[print(a) for a in ans]

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
N = int(input())
v = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    v[a].append([b,i])

ans = [None] * (N-1)

def decide_colord(cur,color):
    cnt = 1
    for (to,j)in v[cur]:
        if cnt == color:
            cnt += 1
        ans[j] = cnt
        decide_colord(to,cnt)
        cnt += 1
decide_colord(0,0)
print(max(ans))
[print(a) for a in ans]
N = int(input())
A = list(map(int, input().split()))

for k in range(N):
    del A[k]
    ans = 0
    
    for i in range(1,N+1):
        n = sum(A[j] == i for j in range(N-1))
        nc2 = n * (n-1) / 2
        ans += nc2
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0 for _ in range(max(a)+1)]
for x in a:
    b[x] += 1
c = sum([x*(x-1)//2 for x in b])
for i in range(n):
    print(c-b[a[i]]+1)
n,d=map(int,input().split())
x=[list(map(int,input().split()))for _ in range(n)]
ans=0
for i in range(n):
    for j in range(i):
        ans+=(sum((a-b)**2 for a,b in zip(x[i],x[j])**0.5)).is_integer()
print(ans)

### FIXED CODE ###

n,d = map(int,input().split())
x = [list(map(int,input().split())) for _ in range(n)]
ans = 0
for i in range(n):
	for j in range(i):
		ans += (sum((a-b)**2 for a,b in zip(x[i],x[j]))**0.5).is_integer()
print(ans)
import itertools
N, a, b, c = [int(_) for _ in input().split()]
L = [int(input()) for _ in range(N)]
ans = float('inf')
for K in itertools.product(range(4), repeat=N):
    A = [[] for _ in range(N)]
    for i in range(N):
        k = K[i]
        A[k] += [L[i]]
    if len(A[1]) and len(A[2]) and len(A[3]):
        cost = 10 * (max(len(A[1]) - 1, 0) + max(len(A[2]) - 1, 0) + max(
            len(A[3]) - 1, 0))
        cost += abs(a - sum(A[1]))
        cost += abs(b - sum(A[2]))
        cost += abs(c - sum(A[3]))
        ans = min(cost, ans)
print(ans)


### FIXED CODE ###

import itertools
N, a, b, c = [int(_) for _ in input().split()]
L = [int(input()) for _ in range(N)]
ans = 10**10
for K in itertools.product(range(4), repeat=N):
    A = [[] for _ in range(4)]
    for i in range(N):
        A[K[i]] += [L[i]]
    if len(A[1]) and len(A[2]) and len(A[3]):
        cost = 10 * (N - len(A[0]) - 3)
        cost += abs(a - sum(A[1]))
        cost += abs(b - sum(A[2]))
        cost += abs(c - sum(A[3]))
        ans = min(cost, ans)
print(ans)
import math
n = int(input())
print(Math.pow(3,n))

### FIXED CODE ###

n = int(input())
p = n**3
print(p)
G = [0] * 4
for i in range(3):
    a, b = mii()
    a -= 1
    b -= 1
    G[a] += 1
    G[b] += 1

for i in range(4):
    if G[i] == 3:
        print('NO')
        exit()

print('YES')


### FIXED CODE ###

G = [0] * 4
for i in range(3):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a] += 1
    G[b] += 1

for i in range(4):
    if G[i] == 3:
        print('NO')
        exit()

print('YES')
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    K = int(input())
    S = str(input())

    #output
    # (o以外) o (o以外) o (f以外) f (何でも)


    #こちらもmodで割った余り。maxが決まっていて、大きくない時はこちらが早い。
    mod = pow(10, 9) + 7

    n_ = pow(10, 6) + 1
    fun = [1] * (n_+1)
    for i in range(1, n_+1):
        fun[i] = fun[i-1] * i % mod
    rev = [1] * (n_+1)
    rev[n_] = pow(fun[n_], mod-2, mod)
    for i in range(n_-1, 0, -1):
        rev[i] = rev[i+1] * (i+1) % mod
    def cmb(n,r):
        if n <= 0 or r < 0 or r > n: return 0
        return fun[n] * rev[r] % mod * rev[n-r] % mod

    #重複組み合わせはH(n, r) = cmb(n+r-1, r)

    N = len(S)
    answer = 0
    for i in range(K+1):
        answer += pow(25, i, mod) * pow(26, K-i, mod) * cmb(N-1+i, N-1) % mod
    print(answer % mod)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

### FIXED CODE ###

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

#input
K = int(input())
S = str(input())

#output
# (o以外) o (o以外) o (f以外) f (何でも)

#こちらもmodで割った余り。maxが決まっていて、大きくない時はこちらが早い。
mod = pow(10, 9) + 7

n_ = 5 * pow(10, 6)
fun = [1] * (n_+1)
for i in range(1, n_+1):
    fun[i] = fun[i-1] * i % mod
rev = [1] * (n_+1)
rev[n_] = pow(fun[n_], mod-2, mod)
for i in range(n_-1, 0, -1):
    rev[i] = rev[i+1] * (i+1) % mod
def cmb(n,r):
    if n < 0 or r < 0 or r > n: return 0
    return fun[n] * rev[r] % mod * rev[n-r] % mod

#重複組み合わせはH(n, r) = cmb(n+r-1, r)

L = len(S)
answer = 0
for i in range(L, L+K+1):
    answer += pow(25, i-L, mod) * pow(26, L+K-i, mod) * cmb(i-1, L-1)
    answer %= mod
print(answer)
x = input()
print(chr(ord(x)+1)

### FIXED CODE ###

x = input()
y = chr(ord(x) + 1)
print(y)
import sys

class Node:
    def __init__(self, id, children):
        self.id = id
        self.parent = -1
        self.depth = 0
        self.type = "root"
        self.children = children

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    N = lines[0]

    tree = []
    for i in range(int(N)):
        tree.append(Node(i, map(int, lines[i + 1][4:].split())))

    for node in tree:
        if not node.children:
            node.type = "leaf"

        for child in node.children:
            tree[child].parent = node.id
            tree[child].depth = node.depth + 1
            if tree[child].type != "leaf"
                tree[child].type = "internal node"

    for node in tree:
        print "node {0.id}: parent = {0.parent}, depth = {0.depth}, {0.type}, {0.children}".format(node)

### FIXED CODE ###

import sys

class Node:
    def __init__(self):
        self.id = id
        self.parent = -1
        self.sibling = -1
        self.type = "leaf"

    def printInfo(self):
        print "node {0.id}: parent = {0.parent}, sibling = {0.sibling}, degree = {0.degree}, depth = {0.depth}, height = {0.height}, {0.type}".format(self)

def setTree(id, tree, depth):
    tree[id].depth = depth
    height = degree = 0
    for i in range(2):
        child = tree[id].children[i]
        if child != -1:
            degree += 1
            tree[child].parent = id
            tree[child].sibling = tree[id].children[~i]
            height = max(setTree(child, tree, depth + 1) + 1, height)
    tree[id].height = height
    tree[id].degree = degree
    if height != 0:
        tree[id].type = "internal node"

    return height

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    N = int(lines[0])
    del lines[0]

    tree = []
    for i in range(N):
        tree.append(Node())

    root = N * (N - 1) / 2
    for line in lines:
        info = map(int, line.split())
        tree[info[0]].children = info[1:]
        tree[info[0]].id = info[0]
        for i in tree[info[0]].children:
            if i != -1:
                root -= i

    setTree(root, tree, 0)
    tree[root].type = "root"

    for node in tree:
        node.printInfo()
import math
A, B, N = map(int, input().split())
if math.floor(N/B)>math.floor(N/(B-1)):
    print(math.floor(A*N/B)-A*math.floor(N/(B-1)))
else:
    print(math.floor(A*N/B)-A*math.floor(N/B))

### FIXED CODE ###

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