Harryxun/stf_run huggingface dataset:
n, k = map(int, input().split())
s = input()
print(s[:k-1]+s[k-1].lower+s[k:])

### FIXED CODE ###

n, k = map(int, input().split())
s = input()
print(s[:k-1]+s[k-1].lower()+s[k:])
import numpy as np
s=[]
tt=[]
n,m=map(int,input().split())
for i in range(n):
    a,b,c=map(int,input().split())
    s.append([a,b,c])
import itertools
t=list(itertools.permutations(s,m))
for i in t:
    total=np.zeros((3))
    for j in range(m):
        total+=np.array(i[j])
        tt.append(abs(total[0])+abs(total[1])+abs(total[2])//1)
print(int(max(tt)))

### FIXED CODE ###

from itertools import product
t=[]
ans=0
n,m=map(int,input().split())
s=list(product([1,-1],repeat=3))
for i in range(n):
    li=[]
    p,q,r=map(int,input().split())
    for a,b,c in s:
        li.append(a*p+b*q+c*r)
    t+=[li]
for j in list(zip(*t)):
    p=sum(sorted(j)[n-m:])
    ans=max(ans,p)
print(ans)
S=input()

if S=='Sunny':
  print("Cloudy)
elif S=='Rainy':
  print('Sunny')
else S=='Cloudy':
  print('Rainy')

### FIXED CODE ###

S=input()
 
if S == 'Sunny':
  print('Cloudy')
elif S == 'Cloudy':
  print('Rainy')
else:
  print('Sunny')
import functools
import sys

n, m = map(int, input().split())
a = list(map(lambda x: x // 2, map(int, input().split())))
a = set(a)

# A[0]を素因数分解して2で割り切れる回数を数える
div = 0

a_0 = a[0]
while a_0 % 2 == 0:
    a_0 /= 2
    div += 1

# print("count = " + str(div))#

# Aのすべての整数がA[0]と同じ回数2で割り切れるか調べる
for i in range(1, len(a)):
    div2 = 0
    a = a[i]
    while a % 2 == 0:
        a /= 2
        div2 += 1
    # print("A[" + str(i) + "] count = " + str(div2))#
    if div2 != div:
        print("0")
        sys.exit()


def gcd(x, y):
    if x == 0:
        return y

    return gcd(y % x, x)


def least_common_multiple(iter):
    '''
    最小公倍数を返す
    '''
    lcm = lambda x, y: x * y // gcd(x, y)
    return functools.reduce(lcm, iter)


lc = least_common_multiple(a)
ans = 0
a = 1

ans = m // lc
if ans == 0:
    print(0)
    sys.exit()
if ans % 2 == 0:
    print(ans // 2)
else:
    print(ans // 2 + 1)


### FIXED CODE ###

import functools
import sys

n, m = map(int, input().split())
a = list(map(lambda x: x // 2, map(int, input().split())))

# A[0]を素因数分解して2で割り切れる回数を数える
div = 0

a_0 = a[0]
while a_0 % 2 == 0:
    a_0 /= 2
    div += 1

# print("count = " + str(div))#

# Aのすべての整数がA[0]と同じ回数2で割り切れるか調べる
for i in range(1, len(a)):
    div2 = 0
    tmp_a = a[i]
    while tmp_a % 2 == 0:
        tmp_a /= 2
        div2 += 1
    # print("A[" + str(i) + "] count = " + str(div2))#
    if div2 != div:
        print("0")
        sys.exit()


def gcd(x, y):
    if x == 0:
        return y

    return gcd(y % x, x)


def least_common_multiple(iter):
    '''
    最小公倍数を返す
    '''
    lcm = lambda x, y: x * y // gcd(x, y)
    return functools.reduce(lcm, iter)


lc = least_common_multiple(a)
ans = 0
a = 1

ans = m // lc
if ans == 0:
    print(0)
    sys.exit()
if ans % 2 == 0:
    print(ans // 2)
else:
    print(ans // 2 + 1)
W,H,x,y=map(str,input().split())

#case1
a=x*H
b=(W-x)*H

if a>=b:
    case1=b
else:
    case1=a

#case2
c=W*y
d=W*(H-y)

if c>=d:
    case2=d
else:
    case2=c

if case1==case2:
    z=1

else:
    z=0

print("{0:.9f}".format(max(case1,case2)),z)


### FIXED CODE ###

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

if x<a:
    print("0")

else:
    print("10")
N = int(input())
s = set()
for i in range(N):
	a,b,c = map(str,input().split(' '))
	e = a + b + c
	e = sorted(d)
	s.add(e)
print(N - len(s))

### FIXED CODE ###

N = int(input())
l = []
s = set()
for i in range(N):
	a,b,c = map(int,input().split(' '))
	l.append(a)
	l.append(b)
	l.append(c)
	l.sort()
	d = str(l[0])
	e = str(l[1])
	f = str(l[2])
	g = d + e + f
	s.add(g)
	l = []
print(N - len(s))
pair_count = 0
for cd_i in cd:
	can_ball_count = 0
	for ab_i in ab:
		if ab_i[0] < cd_i[0] and ab_i[1] < cd_i[1]:
			can_ball_count += 1
		else:
			break
	if 1 <= can_ball_count-pair_count:
		pair_count += 1

print(pair_count)

### FIXED CODE ###

N = int(input())
AB = [list(map(int, input().split(" "))) for _ in range(N)]
CD = [list(map(int, input().split(" "))) for _ in range(N)]

CD.sort()
AB.sort(key=lambda x: (x[1], x[0]), reverse=True)

count = 0
for c, d in CD:
    for j, (a, b) in enumerate(AB):
        if a < c and b < d:
            count += 1
            AB.pop(j)
            break

print(count)
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]
N = n*(n-1)//2
index = [[0]*(n) for i in range(n)]
ind = 0
from collections import defaultdict
ns = defaultdict(list)
for i in range(n):
    for j in range(i+1,n):
        index[i][j] = ind
        index[j][i] = ind
        ind += 1
for i in range(n):
    for j in range(n-2):
        u = index[i][a[i][j]]
        v = index[i][a[i][j+1]]
        ns[u].append(v)
assert False
### サイクル検出 cycle detection
seen = [False] * N
done = [False] * N
vals = [None] * N
def dfs(u):
    s = [u]
    while s:
        u = s.pop()
        if u>=0:
            # 非負の値: 新しい頂点に到達
            seen[u] = True
            s.append(~u)
            for v in ns[u]:
                if done[v]:
                    continue
                elif not seen[v]:
                    s.append(v)
                else:
                    # 閉路発見
                    return True
        else:
            u = ~u
            done[u] = True
            # ここに帰りがけ処理を書く
            val = 0
            for v in ns[u]:
                # uの子はすべて処理が終わっている
                val = max(val, vals[v]+1)
            vals[u] = val
    return False

ans = -float("inf")
for u in range(N):
    if seen[u]:
        continue
    pos = dfs(u)
    if pos:
        print(-1)
        break
else:
    print(max(vals)+1)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]
N = n*(n-1)//2
index = {}
ind = 0
from collections import defaultdict
ns = defaultdict(list)
for i in range(n):
    for j in range(i+1,n):
        index[i,j] = ind
        index[j,i] = ind
        ind += 1
for i in range(n):
    for j in range(n-2):
        u = index[i,a[i][j]]
        v = index[i,a[i][j+1]]
        ns[u].append(v)
### サイクル検出 cycle detection
seen = [False] * N
done = [False] * N
vals = [None] * N
def dfs(u):
    # uからdfs
    seen[u] = True
    ans = 0
    for v in ns[u]:
        if done[v]:
            ans = max(ans, vals[v]+1)
            continue
        elif seen[v]:
            # サイクルを検出
            return 1
        else:
            pos = dfs(v)
            if pos>=0:
                return 1
            ans = max(ans, vals[v]+1)
    done[u] = True
    vals[u] = ans
    return -1
ans = -float("inf")
for u in range(N):
    if seen[u]:
        continue
    pos = dfs(u)
    if pos>=0:
        print(-1)
        break
else:
    print(max(vals)+1)
import sys
input = sys.stdin.readline
n = int(input())
a = [int(s) for s in input().split()]
# a = list(range(1, 2*10**5))
ans = 0
for i,j in enumerate(a):
  a_i = sum(a[i]%s==0 for s in a)
  ans += min([2, a_i])
  # print(min([2, a_i]))
# print('###')
print(n - (ans-n))


### FIXED CODE ###

import sys
input = sys.stdin.readline
a = [int(s) for s in input().split()]
print(a.index(0)+1)
def max_heapify(A, i):
    l = 2 * i
    r = 2 * i + 1
    largest = i
    if l <= len(A) and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r < len(A) and A[r] > A[largest]:
        largest = r

    if largest != i:
        temp = A[i]
        A[i] = A[largest]
        A[largest] = temp
        max_heapify(A, largest)


def build_maxheap(A):
    i = len(A) // 2
    while i >= 1:
        max_heapify(A, i)
        i -= 1


if __name__ == '__main__':
    # ??????????????\???
    num_of_data = int(input())
    A = [int(x) for x in input().split(' ')]
    A.insert(0, 0) # ?????????1??????????????????????????????????????????

    # ???????????????
    build_maxheap(A)
    A = A[1:]  # ???????????????????????????

    # ???????????????
    print(' {0}'.format(' '.join(map(str, A))))

### FIXED CODE ###

def max_heapify(A, i):
    l = 2 * i
    r = 2 * i + 1
    largest = i
    if l < len(A) and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r < len(A) and A[r] > A[largest]:
        largest = r

    if largest != i:
        temp = A[i]
        A[i] = A[largest]
        A[largest] = temp
        max_heapify(A, largest)


def build_maxheap(A):
    i = len(A) // 2
    while i >= 1:
        max_heapify(A, i)
        i -= 1


if __name__ == '__main__':
    # ??????????????\???
    num_of_data = int(input())
    A = [int(x) for x in input().split(' ')]
    A.insert(0, 0) # ?????????1??????????????????????????????????????????

    # ???????????????
    build_maxheap(A)
    A = A[1:]  # ???????????????????????????

    # ???????????????
    print(' {0}'.format(' '.join(map(str, A))))
import heapq

N,M = map(int,input().split())
A = list(map(int,input().split()))
B = [list(map(int,input().split())) for i in range(M)]

B.sort(key=lambda B:B[1],reverse=True)
heapq.heapify(A)

for i in range(M):
    for j in range(B[i][0]):
        c += 1
        if c > N:
            break
        if A[0] < B[i][1]:
            heapq.heappop(A)
            heapq.heappush(A,B[i][1])
            print(A)
        else:
            break
    else:
        continue
    break
    
print(sum(A))

### FIXED CODE ###

import heapq

N,M = map(int,input().split())
A = list(map(int,input().split()))
B = [list(map(int,input().split())) for i in range(M)]

B.sort(key=lambda B:B[1],reverse=True)
heapq.heapify(A)

c = 0
for i in range(M):
    for j in range(B[i][0]):
        c += 1
        if c > N:
            break
        if A[0] < B[i][1]:
            heapq.heappop(A)
            heapq.heappush(A,B[i][1])
            #print(A)
        else:
            break
    else:
        continue
    break
    
print(sum(A))
n = int(input())
S = ["".join(sorted(input())) for _ in range(n)]
d = []
for i in S:
  d.setdefault(i, 0)
  d[i] += 1
ans = 0
for value in d.values:
  ans = value * (value) / 2
print(ans)

### FIXED CODE ###

n = int(input())
S = ["".join(list(sorted(input()))) for _ in range(n)]
d = {}
for i in S:
    d.setdefault(i, 0)
    d[i] += 1
ans = 0
for value in d.values():
    ans += value * (value - 1) / 2
print(int(ans))
import sys
n = input()
intn = int(n)
s = int("1"*len(n))*9
if s==intn:
  print(len(n)*9)
  sys.exit()
ans=int("1"*(len(n)-1))*9
xx = int(n[0])-1
def split(aa):
  return [c for c in aa]
ans=split(str(ans))
c = 0
for i in range(len(ans)):
    ans[c] = int(ans[c])
    c+=1
print(sum(ans)+xx)

### FIXED CODE ###

n = list(map(int, input()))
l = [sum(n)]
for i in range(1, len(n)):
    n[-i] = 9
    n[-i-1] -= 1
    l.append(sum(n)) 
print(max(l))
M,N=map(int,input().split())
X = list(map(int,input().split()))
X.sort()
xdelta = []

for i in range(len(X)-1):
	xdelta.append(X[i+1]-X[i])

xdelta.sort()

for i in range(M-1):
	xdelta.pop(-1)
	
print(sum(xdelta))

### FIXED CODE ###

N,M=map(int,input().split())
X = list(map(int,input().split()))
X.sort()
xdelta = []

for i in range(len(X)-1):
	xdelta.append(abs(X[i+1]-X[i]))

xdelta.sort()

if N < M:
	if N == 1:
		print(sum(xdelta))
	else:
		for i in range(N-1):
			xdelta.pop(-1)
		print(sum(xdelta))
else:
	print(0)
# -*- coding: utf-8 -*-
import math
# スペース区切りの整数の入力
a, b, c = map(int, input().split())
b * math.floor((t+0.5)/a)

### FIXED CODE ###

# -*- coding: utf-8 -*-
a, b, t = map(int, input().split())
print(int(b * ((t+0.5)//a)))
import sys
import collections
import itertools
import numpy as np

n,m = map(int, input().split())
al = np.ones(n,dtype="int8")
H = list(map(int, input().split()))
AB=[]

for i in range(m):
    AB.append(tuple(map(int, input().split())))

for t in range(m):
    A = AB[t][0]
    B = AB[t][1]

    bou1 = H[A-1]
    bou2 = H[B-1]
    if bou1<bou2:
        al[B-1] = al[B-1]-1
    elif bou2<bou1:
        al[A-1] = al[a-1]-1
    else:
        al[A-1] = al[a-1]-1
        al[B-1] = al[B-1]-1
print(np.count_nonzero(al>0))

### FIXED CODE ###

import sys
import collections
import itertools
import numpy as np

n,m = map(int, input().split())
al = np.ones(n,dtype="int8")
H = list(map(int, input().split()))
AB=[]

for i in range(m):
    AB.append(tuple(map(int, input().split())))

for t in range(m):
    A = AB[t][0]
    B = AB[t][1]
	
    bou1 = H[A-1]
    bou2 = H[B-1]
    if bou1<bou2:
        al[A-1] = al[A-1]-1
    elif bou2<bou1:
        al[B-1] = al[B-1]-1
    else:
        al[A-1] = al[A-1]-1
        al[B-1] = al[B-1]-1
print(np.count_nonzero(al==1))
N = input()
  
if N[0] == 7 or N[1] == 7 or N[2] == 7:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

num = input();

if num[0] == "7" or num[1] == "7" or num[2] == "7" :
  print("Yes");
else:
  print("No");
import math

def C(m,n):
    return math.factorial(m)/math.factorial(n)/math.factorial(m-n)

N,K = map(int,input().split())
for i in range(1,K):
    print(C(K-1,i-1)*C(N-K+1,i)/(10**9+7))

### FIXED CODE ###

import math

def C(m,n):
    return math.factorial(m)//math.factorial(n)//math.factorial(m-n)

N,K = map(int,input().split())
for i in range(1,K+1):
    if N-K+1>=i:
        print(int(C(K-1,i-1)*C(N-K+1,i))%(10**9+7))
    else:
        print(0)
R, C, K = map(int, input().split())
rcvs = [tuple(map(int, input().split())) for _ in range(K)]

rcvs.sort(key = lambda t: t[1] * 30000 + t[0])

dp = [[0] * (R+1) for _ in range(4)]
index = 0
for c in range(C+1):
    while index < K and rcvs[index][1] == c:
        x, _, v = rcvs[index]
        if dp[3][x] < dp[2][x] + v:
            dp[3][x] = dp[2][x] + v
        if dp[2][x] < dp[1][x] + v:
            dp[2][x] = dp[1][x] + v
        if dp[1][x] < dp[0][x] + v:
            dp[1][x] = dp[0][x] + v
        if dp[0][x+1] < max((dp[i][x] + v for i in range(4))):
            dp[0][x+1] = max((dp[i][x] + v for i in range(4)))
        index += 1
        #print(dp)   
    
print(max(max(row) for row in dp))


### FIXED CODE ###

R, C, K = map(int, input().split())
points_dict = dict()
for _ in range(K):
    r, c, v = map(int, input().split())
    points_dict[r * 30000 + c] = v

dp = [[[0] * (C+1) for _ in range(R+1)] for _ in range(4)] # dp[4][R+1][C+1]
index = 0
for i in range(1, R+1):
    for j in range(1, C+1):
        #移動
        for k in range(4):
            if dp[0][i][j] < dp[k][i-1][j]:
                dp[0][i][j] = dp[k][i-1][j]
            if dp[k][i][j] < dp[k][i][j-1]:
                dp[k][i][j] = dp[k][i][j-1]
        #あれば、拾うかどうか
        if i * 30000 + j in points_dict:
            v = points_dict[i * 30000 + j]
            for k in range(3, 0, -1):
                if dp[k][i][j] < dp[k-1][i][j] + v:
                    dp[k][i][j] = dp[k-1][i][j] + v
"""
for i in range(4):
    print(i)
    print(*dp[i], sep = '\n')
"""
print(max((dp[i][R][C] for i in range(4))))
def prime_divisor(n):
  prime_divisor_set = {1}
  end = int(n ** 0.5) + 1
  for i in range(2, 10 ** 5 + 1):
    if not (n % i):
      prime_divisor_set.add(i)
      while (n % i) == 0:
        n //= i
  return prime_divisor_set


a, b = map(int, input().split())
s1, s2 = prime_divisor(a), prime_divisor(b)
ans = len(s1 & s2)
print(ans)


### FIXED CODE ###

n = int(input())
if n % 2:
  print((n+1) / (n * 2))
else:
  print(0.5)
A,B=map(int,input()split())
if A>=B*2:
  print(A-B*2)
else:
  print(0)

### FIXED CODE ###

A,B=map(int,input().split())
if A>=(B*2):
   print(A-(B*2))
else:
   print(0)
s=input()
res="AC"
if s[0]=="A":res="WA"
elif s[2:-2].count("C")!=1:res="WA"
else:
    li=list(s)
    li.remove("A")
    li.remove("C")
    for i in li:
        if i!=i.lower():
            res="WA"
print(res)

### FIXED CODE ###

s=input()
res="AC"
if s[0]!="A":res="WA"
elif s[2:-1].count("C")!=1:res="WA"
else:
    li=list(s)
    li.remove("A")
    li.remove("C")
    for i in li:
        if i!=i.lower():
            res="WA"
print(res)
S = input()
if(S[0]=="A" and S.find("C") != -1):
    S = S.replace("C","c")
    ans = S[1:].islower()
if(ans):
    print("AC")
else:
    print("WA")

### FIXED CODE ###

S = input()
ans = False
if(S[0]=="A" and S[2:len(S)-1].find("C") != -1 and S.count("C") == 1):
    S = S.replace("C","c")
    ans = S[1:].islower()
if(ans):
    print("AC")
else:
    print("WA")
import numpy as np


D = int(input())
c = np.array(list( map(int,input().split())))
S = np.zeros((D,26))
for i in range(D):
    S[i] = np.array(list( map(int,input().split())))

T = np.array([])
for i in range(D):
    T = np.append(T,int(input()))

"""
D = 365
c = np.random.randint(0,100,size=(26))
S = np.random.randint(0,20000,size=(D,26))
"""

def calc_score(T,D,c,S):
    last = np.ones(26) * (-1)
    scores = []
    score = 0
    for d in range(D):
        i = int(T[d])
        score += S[d,i]
        last[i] = d
        score -= np.sum(c*(d-last))
        scores.append(max([10**6+score,0]))
    score = max([10**6+score,0])
    return score,scores

_,ans = calc_score(T,D,c,S)
for a in ans:
    print(int(a))

### FIXED CODE ###

import numpy as np


D = int(input())
c = np.array(list( map(int,input().split())))
S = np.zeros((D,26))
for i in range(D):
    S[i] = np.array(list( map(int,input().split())))

T = np.array([])
for i in range(D):
    T = np.append(T,int(input()))

"""
D = 365
c = np.random.randint(0,100,size=(26))
S = np.random.randint(0,20000,size=(D,26))
"""

def calc_score(T,D,c,S):
    last = np.ones(26) * (-1)
    scores = []
    score = 0
    for d in range(D):
        i = int(T[d])-1
        score += S[d,i]
        last[i] = d
        score -= np.sum(c*(d-last))
        scores.append(score)
    score = max([10**6+score,0])
    return score,scores

_,ans = calc_score(T,D,c,S)
for a in ans:
    print(int(a))
N, M = [int(a) for a in input().split()]
S = [[int(i) for i in input().split()] for _ in range(M)]
flag = 0
if([1,0] in S):
    flag = 1
    print(-1)
else:
    NUM = 0
    LIST = [-1 for _ in range(M)]
    for s,c in S:
        s -= 1
        if(LIST[s]==-1):
            NUM += c*(10**(N-s-1))
            LIST[s] = c
        else:
            if(LIST[s]!=c):
                flag = 1
                print(-1)
                break
            else:
                continue
    if(LIST[0] == -1):
        if(N>1):
            NUM += 10**(N-1)
        else:
            NUM = 0
    if(flag==0):
        print(NUM)

### FIXED CODE ###

N, M = [int(a) for a in input().split()]
S = [[int(i) for i in input().split()] for _ in range(M)]
flag = 0
NUM = 0
LIST = [-1 for _ in range(N)]
for s,c in S:
    s -= 1
    if(LIST[s]==-1):
        NUM += c*(10**(N-s-1))
        LIST[s] = c
    else:
        if(LIST[s]!=c):
            flag = 1
            print(-1)
            break
        else:
            continue
if(LIST[0] == -1):
    if(N>1):
        NUM += 10**(N-1)
    else:
        NUM = 0
elif(LIST[0] == 0):
    if(N>1):
        print(-1)
        flag = 1
    else:
        NUM = 0
if(flag==0):
    print(NUM)
import itertools
n,m=map(int,input().split())
p=[[False]*n for i in range(n)]
ans=0
for i in range(n):
    a,b=map(int,input().split())
    a-=1
    b-=1
    p[a][b]=True
    p[b][a]=True

for i in itertools.permutations(range(n),n):
    if i[0]==0:
        for j in range(n):
            if j==n-1:
                ans+=1
                break
            if not p[i[j]][i[j+1]]:
                break
print(ans)

### FIXED CODE ###

import itertools
n,m=map(int,input().split())
p=[[False]*n for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    p[a][b]=True
    p[b][a]=True
ans=0
for i in itertools.permutations(range(n),n):
    if i[0]==0:
        for j in range(n):
            if j==n-1:
                ans+=1
                break
            if not p[i[j]][i[j+1]]:
                break
print(ans)
n,d = map(int,input().split())
cnt = 0
for i in raneg(n):
    p,q = map(int,input().split())
    cnt += p*p+q*q <= d*d
print(cnt)

### FIXED CODE ###

n,d = map(int,input().split())
cnt = 0
for i in range(n):
    p,q = map(int,input().split())
    cnt += p*p+q*q <= d*d
print(cnt)
from sympy import isprime


i=int(input())
judge=not isprime(i)
while judge:
    i+=1
    judge=not isprime(i)
print(i)

### FIXED CODE ###

import math
 

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


X=int(input())
judge=not is_prime(X)
while judge:
    X+=1
    judge=not is_prime(X)
    
print(X)
def neighbor(N, edges):
    neighbor_list = [[] for _ in range(N)]
    for i in range(N):
        for vs in edges:
            if i + 1 in vs: # vsは頂点i+1が含まれるedge
                neighbor_list[i] += vs
        neighbor_list[i] = list(set(neighbor_list[i]))
        neighbor_list[i].remove(i + 1)
        
    return neighbor_list

def neighbor2(N, edges):
    nlist = neighbor(N, edges)
    nneighbor_list = [[] for _ in range(N)]
    for i in range(N):
        nneighbor_list[i] += nlist[i]
        for e in nlist[i]:
            nneighbor_list[i] += nlist[e - 1]
        nneighbor_list[i] = list(set(nneighbor_list[i]))
        nneighbor_list[i].remove(i + 1)
    return nneighbor_list
        
        
def combination(N, K, nnlist):
    combi = 1
    clist = [False]*N
    for v in range(N):
        print(combi)
        combi *= (K - len([t for t in nnlist[v] if clist[t-1]]))
        clist[v] = True
    return combi

def paint(N, K, nlist, nnlist, clist, vlist, combi):
    vlist_next = []
    for v in vlist:
        #nnlistの中で塗られている頂点の数を数え、色候補数Kから引く
        combi *= (K - len([t for t in nnlist[v - 1] if clist[t - 1]])) 
        clist[v - 1] = True #頂点vを塗る
        vlist_next += [t for t in nlist[v - 1] if not clist[t - 1]]
    return combi, vlist_next, clist


if __name__ == '__main__':
    N, K = map(int, input().split())
    edges = [None]*(N-1)
    
    for i in range(N-1):
        edges[i] = list(map(int, input().split()))
    
    nlist = neighbor(N, edges)
    nnlist = neighbor2(N, edges)
    


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def neighbor(N, edges):
    neighbor_list = [[] for _ in range(N)]
    for a, b in edges:
        neighbor_list[a-1] += [b-1]
        neighbor_list[b-1] += [a-1]
        
    return neighbor_list


def paint(K, nlist, now_num, from_num, case_num):
        mod = 1000000007
        if  from_num == -1:
            can_use_color = K - 1
        else:
            can_use_color = K - 2
        
        if len(nlist[now_num]) - 1 > can_use_color:
            return 0
        
        for child in nlist[now_num]:
            if child == from_num:
                continue
            else:
                case_num *= can_use_color
                can_use_color -= 1
                case_num %= mod
        
        for child in nlist[now_num]:
            if child == from_num:
                continue
            else:
                case_num = paint(K, nlist, child, now_num, case_num)
        return case_num%mod
            

if __name__ == '__main__':
    N, K = map(int, input().split())
    edges = [None]*(N-1)
    
    for i in range(N-1):
        edges[i] = list(map(int, input().split()))
    
    nlist = neighbor(N, edges)


    print(paint(K, nlist, 0, -1, K))
a, b = map(int, input())
print(max(a+b, 2*a-1, 2*b-1))

### FIXED CODE ###

a, b = map(int, input().split())
print(max(a+b, 2*a-1, 2*b-1))