Harryxun/stf_run huggingface dataset:
def dfs(current, prev):
    for next in g[current]:
        if next != prev:
            if visited[next]:
                ki = False
            else:
                visited[next] = True
                dfs(next, now)


n, m = map(int, input().split())
g = [[] * n for i in range(n)]
ans = 0
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
visited = [False for i in range(n)]
for i in range(n):
    if not visited[i]:
        ki = True
        dfs(i, -1)
        if ki:
            ans += 1
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
n, q = map(int, input().split())
edges = [[] for i in range(n)]
counter = [0] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
for i in range(q):
    p, x = map(int, input().split())
    counter[p - 1] += x
def dfs(now, prev):
    for next in edges[now]:
        if next == prev:
            continue
        counter[next] += counter[now]
        dfs(next, now)
dfs(0, -1)
print(*counter)
a,b = map(int,input())
dp = [0 for i in range(b+1)]
for i in range(a):
    x,y = map(int,input())
    for j in range(b,y+1,y):
        pp = x + dp[j-y]
        if pp > dp[j]:
            dp[j] = pp
            
print(max(dp))
    


### FIXED CODE ###

N, W = map(int, input().split())
dp = [0] + [W+1] * (N*100)
for i in range(N):
    v, w = map(int, input().split())
    for j in range(i*100, -1, -1):
        if dp[j+v] > dp[j] + w:
            dp[j+v] = dp[j] + w

for v, w in zip(range(N*100, -1, -1), dp[::-1]):
    if w < W+1:
        print(v)
        break
import bisect
N = int(input())
A = [0 for i in range(N)]
for i in range(N):
    A[i] = int(input())
now = [-A[0]]
 
for i in range(1, N):
 
    index = bisect.insort_right(now, -A[i])
    if index == len(now):
        now.append(-A[i])
    else:
        now[index] = -A[i]
 
print(len(now))

### FIXED CODE ###

import bisect
N = int(input())
A = [0 for i in range(N)]
for i in range(N):
    A[i] = int(input())
now = [-A[0]]
 
for i in range(1, N):
 
    index = bisect.bisect_right(now, -A[i])
    if index == len(now):
        now.append(-A[i])
    else:
        now[index] = -A[i]
print(len(now))
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
A.sort()


ans = 0
for i in range(N):
    if D[A[i]] == 1:
        flag=True
        cnt=0
        for j in range(i):
            if A[i] % A[j] == 0:
                cnt+=1

            if A[j]**2 > A[i]:
                break
        if cnt==1:
            ans += 1
    else:
        pass
    
print(ans)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
visited=[False for i in range(10**6+1)]
ban=[False for i in range(10**6+1)]
from collections import Counter
A.sort()
D=dict(Counter(A))
for n in A:
    if visited[n]==False:
        visited[n]=True
        for j in range(2,10**6):
            if 10**6<n*j:
                break 
            ban[n*j]=True
ans=0
for n in A:
    if D[n]==1 and ban[n]==False:
        ans+=1
print(ans)
S = imput()
if S == "Sunny":
  print("Cloudy")
elif S == "Cloudy":
  print("Rainy")
else:
  print("Sunny")

### FIXED CODE ###

S = input()
if S == "Sunny":
  print("Cloudy")
elif S == "Cloudy":
  print("Rainy")
else:
  print("Sunny")
N=int(input())
import math
power=1
for i in range(0,n):
  power=power*(i+1)
print(power%(10**9+7))

### FIXED CODE ###

N=int(input())
import math
power=math.factorial(N)
print(power%(10**9+7))
a = input()
if a == 'hi' or a == 'hihi' or a == 'hihihi' or a == 'hihihihi' or a == 'hihihihihi' or a == 'hihihihihi' or 
  print('Yes')
else:
  print('No')

### FIXED CODE ###

a = input()
if a == 'hi' or a == 'hihi' or a == 'hihihi' or a == 'hihihihi' or a == 'hihihihihi' or a == 'hihihihihi':
  print('Yes')
else:
  print('No')
import math
import functools
from operator import add

def main():
    h,w,k = tuple([int(t)for t in input().split()])

    s = [[int(i) for i in list(input())] for _ in range(h)]
    
    cusum = [accumelist(s_) for s_ in s]

    candidates = []

    for i in range(1<<(h-1)):
        subcu = divide(cusum,i)
        subcusum = []

        for sub_ in subcu:
            subcusum.append(functools.reduce((lambda a,b:list(map(add,a,b))),sub_))

        cutnum = 0
        j=0
        temp = [0]*len(subcusum)

        while j<w:
            for l in range(len(subcusum)):
                pos = 0
                if subcusum[l][j]-temp[l]>k:
                    pos = j
                    j-=1
                    if j-pos==0:
                        cutnum+=10000
                    temp = [x[j-1] for x in subcusum]
                    cutnum+=1
                    break
            j+=1
        
        candidates.append(cutnum+bin(i).count('1'))

    print(min(candidates))
            
def divide(s,i):
    subs = []
    counter = 0
    pos = 0
    while i!= 0:
        counter +=1
        if i%2==1:
            subs.append(s[pos:counter])
            pos = counter
        i >>=1
 
    subs.append(s[pos:])
    return subs

def accumelist(s):
    if s == []:
        return []
    res = [s[0]]
    for i in range(1,len(s)):
        res.append(res[i-1]+s[i])

    return res

def _add_(a,b):
    return map(add,a,b)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n,m = tuple([int(t)for t in input().split()])

    print(n*(n-1)//2+m*(m-1)//2)

if __name__ == "__main__":
    main()
A=int(input())
B=int(input())

answer1=A+B
answer2=A-B
answer3=A*B

print(max(answer1,answer2,answer3))

### FIXED CODE ###

A,B=map(int,input().split())
print(max(A+B,A-B,A*B))
s=sorted(input())
print("Yes" if s[0]==s[1] and s[2]==s[3 else "No"])


### FIXED CODE ###

s=sorted(input())
print("Yes" if s[0]==s[1] and s[2]==s[3] and s[0]!=s[2] else "No")
n=int(input())
alist=list(map(int, input().split()))
blist=[]
for i in range(n):
  blist.append(alist[i]-i-1)
blist.sort()
if n%2==1:
  cnt=0
  for i in range(n):
    cnt+=abs(blist[i]-blist[(i+1)//2])
  print(cnt)
else:
  cnt=0
  num=(blist[i//2]+blist[i//2+1])//2
  for i in range(n):
    cnt+=abs(blist[i]-num
  print(cnt,cnt2)

### FIXED CODE ###

import statistics
n=int(input())
alist=list(map(int, input().split()))
blist=[]
for i in range(n):
  blist.append(alist[i]-i-1)
blist.sort()
median=statistics.median_high(blist)
ans=0
for i in range(n):
  ans+=abs(blist[i]-median)
print(ans)
L, R, d = map(int, input().split())
count = 0
for L in range(L, M):
  if (L%2 == 0):
    count +=1
    
  
print(count)


### FIXED CODE ###

L, R, d = map(int, input().split())
count = 0
if ((L and R and d >=1) and (L and R and d <= 100) ):
    for L in range(L, R+1):
        if (L%d == 0):
            count +=1
    print(count)
from heapq import heappush
N,M = map(int, input().split())
A = {}
prefs = []
years = []
for i in range(M):
    p,y = input().split()
    prefs.append(p)
    years.append(y)
    if p not in A:
        A[p] = [y]
    else:
        heappush(A[p], y)
res = {}
for k,v in A.items():
    for i in range(len(v)):
        res[k+v[i]] = str(i+1)
for p,y in zip(prefs, years):
    print(p.zfill(6) + res[k+y].zfill(6))


### FIXED CODE ###

from heapq import heappush, heappop
N,M = map(int, input().split())
A = {}
prefs = []
years = []
for i in range(M):
    p,y = input().split()
    prefs.append(p)
    years.append(y)
    if p not in A:
        A[p] = [int(y)]
    else:
        heappush(A[p], int(y))
res = {}
for k,v in A.items():
    for i in range(len(v)):
        res[k+str(heappop(v))] = str(i+1)
for p,y in zip(prefs, years):
    print(p.zfill(6) + res[p+y].zfill(6))
def nCr(n,r):
    nk = 1
    nrk = 1
    rk = 1
    for i in range (n):
        nk *= i + 1
    for i in range (n-r):
        nrk *= i + 1
    for i in range (r):
        rk *= i + 1
    return int(nk/(nrk*rk))

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


### FIXED CODE ###

def nCr(n,r):
    com = 1
    for i in range (1,r+1):
        com =com*(n+1-i)//i
    return com
N,K = map(int,input().split())
mod = (10**9)+7
for i in range(1,K+1):
    com1 = nCr(N - K + 1, i)
    com2 = nCr(K-1,i-1)
    print((com1*com2)%mod)
N = int(input())
INF = 10**10
cost = [[INF]*N for _ in range(N)]

for u in range(N):
    C = list(map(int, input().split()))
    for v in range(N):
        if u==v: # INFのままにする
            continue
        cost[u][v] = C[u]
 
ans = 0
for u in range(N):
    for v in range(j+1,N):
        mn = INF # u-w-vのような経路の中で最小の距離を求める
        for w in range(N):
            mn = min(mn, cost[u][w]+cost[w][v])    
        if (cost[u][v] > mn): # 与えられた行列が最短経路ではない
            print (-1)
            exit()
        elif (cost[u][v] < mn): # 等しくない場合はu-vを直接結ぶ橋が必要 
            ans += cost[u][v]                      
print (ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7

N = int(input())
INF = 10**10
cost = [[INF]*N for _ in range(N)]

for i in range(N):
    C = list(map(int, input().split()))
    for j in range(N):
        cost[i][j] = C[j]
    cost[i][i] = INF

ans = 0
for j in range(N):
    for k in range(j+1,N):
        mn = INF
        for i in range(N):
            mn = min(mn, cost[j][i]+cost[i][k])    
        if (cost[j][k] > mn):
            print (-1)
            exit()
        elif (cost[j][k] < mn):
            ans += cost[j][k]                      
print (ans)
import copy

S = list(input())
K = int(input())

def Scount():
    cnt_S = 0
    for i in range(len(S)-1):
        if S[i] == S[i+1]:
            S[i+1] = "1"
            cnt_S += 1
    return cnt_S

if K == 1:
    ans = Scout()

else:
    T = copy.copy(S)
    T.insert(0, T[len(T)-1])
    cnt_T = 0
    for i in range(len(T)-1):
        if T[i] == T[i+1]:
            T[i+1] = "1"
            cnt_T += 1

    if T[i+1] != "1":
        ans = Scount() + (cnt_T * (K-1))
    else:
        TT = S * 2
        cnt_T = 0
        for i in range(len(TT)-1):
            if TT[i] == TT[i+1]:
                TT[i+1] = "1"
                cnt_T += 1
        if K % 2 == 0:
            ans = cnt_T * K / 2
        else:
            ans = (cnt_T * K // 2) + Scount()

print(ans)

### FIXED CODE ###

import copy

S = list(input())
K = int(input())

def Scount():
    cnt_S = 0
    for i in range(len(S)-1):
        if S[i] == S[i+1]:
            S[i+1] = "1"
            cnt_S += 1
    return cnt_S

T = copy.copy(S)
T.insert(0, T[len(T)-1])
cnt_T = 0
for i in range(len(T)-1):
    if T[i] == T[i+1]:
        T[i+1] = "1"
        cnt_T += 1

if T[i+1] != "1":
    ans = Scount() + (cnt_T * (K-1))
else:
    TT = S * 2
    cnt_T = 0
    for i in range(len(TT)-1):
        if TT[i] == TT[i+1]:
            TT[i+1] = "1"
            cnt_T += 1
    if K % 2 == 0:
        ans = cnt_T * (K // 2)
    else:
        ans = (cnt_T * (K // 2)) + Scount()
print(ans)
# -*- coding: utf-8 -*-
x = raw_input()
mylist = list(x)

if mylist[2] == mylist[3] and mylist[4] == mylist[5]:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

# -*- coding: utf-8 -*-
x = input()
mylist = list(x)

if mylist[2] == mylist[3] and mylist[4] == mylist[5]:
  print('Yes')
else:
  print('No')
n=int(input())
l=list(map(int,input().split()))
if min(l)== 0:
    print(0)
else:    
    s=1
    for x in l:
        s *= x
        if s>1000000000000000000:
            s=1
            
print(s)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
if min(l)== 0:
    print(0)
else:    
    s=1
    for x in l:
        s *= x
        if s>10**18:
            s=-1
            break
    print(s)
a = map(int, input().split())

if a%10==3:
  print("bon")
elif a%10 in [0,1,6,8]:
  print("pon")
else:
  print("hon")
  

### FIXED CODE ###

a = int(input())

if a%10==3:
  print("bon")
elif a%10 in [0,1,6,8]:
  print("pon")
else:
  print("hon")
import bisect
s = list(input())
t = list(input())
n = len(s)
m = len(t)
alphabet = [[] for _ in range(26)]
for i in range(n):
  alphabet[ord(s[i])-ord('a')+1] += [i] 

loop = 0
pre = -1
for i in range(m):
  c = ord(t[i]) - ord('a') + 1
  idx = bisect.bisect_left(alphabet[c], pre+1)
  if idx == len(alphabet[c]):
    loop += 1
    pre = alphabet[c][0]
  else:
    pre = alphabet[c][idx]

print(pre + loop * n + 1)



### FIXED CODE ###

import bisect
s = list(input())
t = list(input())
n = len(s)
m = len(t)
alphabet = [[] for _ in range(26)]
for i in range(n):
  alphabet[ord(s[i])-ord('a')] += [i] 
loop = 0
pre = -1
for i in range(m):
  c = ord(t[i]) - ord('a')
  if len(alphabet[c]) == 0:
    print(-1)
    exit()
  idx = bisect.bisect_left(alphabet[c], pre+1)
  if idx == len(alphabet[c]):
    loop += 1
    pre = alphabet[c][0]
  else:
    pre = alphabet[c][idx]

print(pre + loop * n + 1)
s=input()
f=int(s[:2])
b=int(s[3:])
if f>13:
	if 0<b and b<13:
		print("YYMM")
	else:
		print("NA")
else:
	if 0<b and b<13:
		print("AMBIGUOUS")
	else:
		prinr("MMYY")

### FIXED CODE ###

s=input()
f=int(s[:2])
b=int(s[2:])
if f>=13 or f==0:
	if 0<b and b<13:
		print("YYMM")
	else:
		print("NA")
elif 0<f and f<13:
	if 0<b and b<13:
		print("AMBIGUOUS")
	else:
		print("MMYY")
else:
	print("NA")
a,b = map(int,input().split)
if((a + b) % 2 == 0):
    print((a + b) / 2)
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

a,b = map(int,input().split())
if((a + b) % 2 == 0):
    print((a + b) // 2)
else:
    print('IMPOSSIBLE')
while True:
	try:
		a,b,c,d,e,f = map(float,raw_input().split())
		x = (e*c-b*f) / (e*a-b*d)
		y = (c*d-a*f) / (b*d-e*a)
		if x == -0.0:
			x = 0
		if y == -0.0
			y = 0
		print '%.3f %.3f' % (x,y)
	except EOFError:
		break

### FIXED CODE ###

while True:
	try:
		a,b,c,d,e,f = map(float,raw_input().split())
		x = (e*c-b*f) / (e*a-b*d)
		y = (c*d-a*f) / (b*d-e*a)
		if x == -0.0:
			x = 0
		if y == -0.0:
			y = 0
		print '%.3f %.3f' % (x,y)
	except EOFError:
		break
a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print a[int(input)-1]

### FIXED CODE ###

a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(a[int(input())-1])
n=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
print("Yes" if a[0]-b[0]==a[1]-b[1]==a[2]-b[2] and a[0]-c[0]==a[1]-c[1]==a[2]-c[2] else "No")

### FIXED CODE ###

a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
print("Yes" if a[0]-b[0]==a[1]-b[1]==a[2]-b[2] and a[0]-c[0]==a[1]-c[1]==a[2]-c[2] else "No")
import sys
import bisect


class SegmentTree(object):  #1-indexed
    def __init__(self, size, value):
        self.len = 1 << size.bit_length()
        self.default = value
        # print(self.len)
        self.array = [value] * (2 * self.len)

    def get(self, i):
        i += self.len
        ans = self.default
        while i > 0:
            ans = min(self.array[i], ans)
            i >>= 1
        return ans

    def query(self, l, r, v, i, a, b):
        if self.array[i] != self.default:
            return 0
        if l == a and r == b:
            self.array[i] = v
            return 0
        center = (a + b) // 2
        if center >= r:
            return self.query(l, r, v, i * 2, a, center)
        elif center <= l:
            return self.query(l, r, v, i * 2 + 1, center, b) 
        else:
            return min(
                self.query(l, center, v, i * 2, a, center),
                self.query(center, r, v, i * 2 + 1, center, b))

    def update(self, l, r, v):
        return self.query(l, r, v, 1, 0, self.len)


input = sys.stdin.readline

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

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

STX_array = sorted(STX_array, key=lambda x: x[2])

Q_array = [int(input()) for _ in range(Q)]

index_array = [i for i in range(Q)]

INF = 10**9 + 7

seg_tree = SegmentTree(Q, INF)

for STX in STX_array:
    s, t, x = STX
    index_left = bisect.bisect_left(Q_array, s - 0.5 - x)
    index_right = bisect.bisect_left(Q_array, t - 0.5 - x)
    seg_tree.update(index_left, index_right, x)

for i in range(Q):
    ans = seg_tree.get(i)
    print(ans) if ans != INF else print(-1)

### FIXED CODE ###

import sys
import bisect

input = sys.stdin.readline

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

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

STX_array = sorted(STX_array, key=lambda x: x[2])

Q_array = [int(input()) for _ in range(Q)]

index_array = [i for i in range(Q)]

ans_array = [-1] * Q
for STX in STX_array:
    s, t, x = STX
    index_left = bisect.bisect_left(Q_array, s - 0.5 - x)
    index_right = bisect.bisect_left(Q_array, t - 0.5 - x)
    if index_left != index_right:
        now_index = index_left
        while now_index < index_right:
            if index_array[now_index] == now_index:
                ans_array[now_index] = x
                index_array[now_index] = index_right
                now_index += 1
            else:
                old_index = now_index
                now_index = index_array[now_index]
                index_array[old_index] = now_index




for ans in ans_array:
    print(ans)
a, b = map(int, input().split())
c = []
d = ""
for i in range(a):
    c.append(list(input()))
for i in range(b):
    d += input()
e = []
for i in range(b):
    for j in range(b):
        f = ""
        for k in range(b):
            for l in range(b):
                f += c[i+k][j+l]
        e.append(f)
print("Yes" if d in e else "No")


### FIXED CODE ###

a, b = map(int, input().split())
c = []
d = ""
for i in range(a):
    c.append(list(input()))
for i in range(b):
    d += input()
e = []
for i in range(a-b+1):
    for j in range(a-b+1):
        f = ""
        for k in range(b):
            for l in range(b):
                f += c[i+k][j+l]
        e.append(f)
print("Yes" if d in e else "No")
import sys
import fractions
from functools import reduce
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

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

N, M = map(int, input().split())
a = [int(x) for x in input().split()]

ans = 0
half_lcm = lcm_list(a) // 2

a = set(a)
for i in range(half_lcm, M+1, half_lcm):
    if all(int((i / x * 2)) & 1 for x in a):
        ans += 1

print(ans)

### FIXED CODE ###

import sys
# import fractions
import math
from functools import reduce
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
stdin = sys.stdin

def gcd(a,b):
  while b:a,b=b,a%b
  return a

def lcm(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(l):
    return reduce(lcm, l, 1)

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

N, M = i_l()
a = i_l()
half_lcm = lcm_list(a) // 2

for i in a:
    if half_lcm // (i // 2) % 2 == 0:
        print(0)
        exit()

print(((M // half_lcm) + 1) // 2)
import math
x,y=input().split()
print(int(math.log(2,int(y)//int(x))+1))

### FIXED CODE ###

x,y=input().split();
k,w=int(y)//int(x),0
while 2**w<=k:w=w+1
print(w)
n, m = [int(i) for i in input().split()]
fibo_l = [1, 1] + [None] * n
a = [int(input()) for i in range(m)]

def fibo(x):
    if x not in a and x >= 0:
            if fibo_l[x] is None:
                fibo_l[x] = fibo(x - 1) + fibo(x - 2)
                return fibo_l[x]
            else: return fibo_l[x]
    else: return 0
    
print(fibo(n) % 1000000007)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

n, m = [int(i) for i in input().split()]
fibo_l = [1] + [None] * n
a = set([int(input()) for i in range(m)])

def fibo(x):
    if x not in a and x >= 0:
            if fibo_l[x] is None:
                fibo_l[x] = fibo(x-1) % 1000000007 + fibo(x-2) % 1000000007
            return fibo_l[x]
    else: return 0
    
print(fibo(n) % 1000000007)
a = int(input())
s = input()
print(s if a >= 3200 else 'red)

### FIXED CODE ###

a = int(input())
s = input()
print(s if a >= 3200 else 'red')
from itertools import accumulate

input()
l = [0, *accumulate(c == '.' for c in input())]
print(min(i - x + l[-1] - x for i, x in enumerate(l)))


### FIXED CODE ###

from itertools import accumulate
 
input()
l = [0] + list(accumulate(c == '.' for c in input()))
print(min(i - x + l[-1] - x for i, x in enumerate(l)))
y = sorted(input().split())
if (y[0] == y[1]) and(y[2]== y[3]):
    print('YES')
else:
    print('NO')

### FIXED CODE ###

y = sorted(list(input()))

if (y[0] == y[1]) and(y[2]== y[3])and(y[0]!=y[2]):
    print('Yes')
else:
    print('No')
n,k,q=map(int,input().split())
diff=q-k
count=[0]*n
arr=[int(input()) for _ in range(n)]
ans=['No']*n
for i in range(n):
  count[arr[i]-1]+=1
for i in range(n):
  if count[i]>diff:
    ans[i]='Yes'
  print(ans[i])

### FIXED CODE ###

n,k,q=map(int,input().split())
diff=q-k
count=[0]*n
arr=[int(input()) for _ in range(q)]
ans=['No']*n
for i in range(q):
  count[arr[i]-1]+=1
for i in range(n):
  if count[i]>diff:
    ans[i]='Yes'
  print(ans[i])
N, K = map(int, input().split())
S = input()

H = 0
N_LR = 0
N_RL = 0

if S[0] == 'R' and S[1] == 'R':
    H += 1
if S[0] == 'R' and S[1] == 'L':
    N_RL += 1
if S[0] == 'L' and S[1] == 'R':
    N_LR += 1

if S[N-1] == 'L' and S[N-2] == 'L':
    H += 1

for i in range(1, N-1):
    if S[i] == 'L' and S[i-1] == 'L' or S[i] == 'R' and S[i+1] == 'R':
        H += 1
    if S[i] == 'R' and S[i+1] == 'L':
        N_RL += 1
    if S[i] == 'L' and S[i+1] == 'R':
        N_LR += 1

M = min(N_RL, N_LR, K)
H += 2 * M
K -= M
N_RL -= M
N_LR -= M

s0 = S[0]
while K > 0:
    if s0 == 'R' and N_RL > 0:
        H += 1
        s0 = 'L'
        N_RL -= 1
        K -=1
    elif s0 == 'L' and N_LR > 0:
        H += 1
        s0 = 'R'
        N_LR -= 1
        K -=1

sN = S[N-1]
while K > 0:
    if sN == 'R' and N_LR > 0:
        H += 1
        sN = 'L'
        N_LR -= 1
        K -=1
    elif sN == 'L' and N_RL > 0:
        H += 1
        sN = 'R'
        N_RL -= 1
        K -=1

print(H)


### FIXED CODE ###

N, K = map(int, input().split())
S = input()

if N == 1:
    print(0)
else:
    H = 0
    N_LR = 0
    N_RL = 0

    if S[0] == 'R' and S[1] == 'R':
        H += 1
    if S[0] == 'R' and S[1] == 'L':
        N_RL += 1
    if S[0] == 'L' and S[1] == 'R':
        N_LR += 1

    if S[N-1] == 'L' and S[N-2] == 'L':
        H += 1

    for i in range(1, N-1):
        if S[i] == 'L' and S[i-1] == 'L' or S[i] == 'R' and S[i+1] == 'R':
            H += 1
        if S[i] == 'R' and S[i+1] == 'L':
            N_RL += 1
        if S[i] == 'L' and S[i+1] == 'R':
            N_LR += 1

    M = min(N_RL, N_LR, K)
    H += 2 * M
    K -= M
    N_RL -= M
    N_LR -= M

    s0 = S[0]
    while K > 0 and (s0 == 'R' and N_RL > 0 or s0 == 'L' and N_LR > 0):
        if s0 == 'R' and N_RL > 0:
            H += 1
            s0 = 'L'
            N_RL -= 1
            K -=1
        elif s0 == 'L' and N_LR > 0:
            H += 1
            s0 = 'R'
            N_LR -= 1
            K -=1

    sN = S[N-1]
    while K > 0 and (sN == 'R' and N_LR > 0 or sN == 'L' and N_RL > 0):
        if sN == 'R' and N_LR > 0:
            H += 1
            sN = 'L'
            N_LR -= 1
            K -=1
        elif sN == 'L' and N_RL > 0:
            H += 1
            sN = 'R'
            N_RL -= 1
            K -=1

    print(H)