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

from collections import deque

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

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def find(s, t):
    global g
    queue = deque()
    queue.append((0, s))
    queue.append((1, t))
    visited = ([0] * n, [0] * n)
    visited[0][s] = 1
    visited[1][t] = 1

    def remember(visited, new):
        for i, v in enumerate(visited):
            if v:
                g[new].add(i)
                g[i].add(new)
        visited[new] = 1

    while queue:
        st, i = queue.popleft()
        for f in g[i]:
            if visited[not st][f]:
                return True
            if not visited[st][f]:
                remember(visited[st], f)
                queue.append((st, f))
    return False


q = int(input())
while q:
    s, t = map(int, input().split())
    print('yes' if find(s, t) else 'no')
    q -= 1

### FIXED CODE ###

n, m = map(int, input().split())
g = [set() for _ in range(n)]
group_ids = [0] * n

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def search(s, gid):
    global g, group_ids
    queue = set(g[s])
    group_ids[s] = gid

    while queue:
        i = queue.pop()
        if not group_ids[i]:
            group_ids[i] = gid
            queue.update(g[i])


gid = 1
for i in range(n):
    if group_ids[i]:
        continue
    search(i, gid)
    gid += 1

q = int(input())
while q:
    s, t = map(int, input().split())
    gs, gt = group_ids[s], group_ids[t]
    print('yes' if gs and gt and gs == gt else 'no')
    q -= 1
### BUGGY CODE ###

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

cumpro=[]

pro=1
for i in range(n):
    pro*=a[i]
    cumpro.append(pro)

ans=[cumpro[k-1]]

for j in range(k,n):
    ans.append(cumpro[j]/cumpro[j-k])

for m in range(1,len(ans)):
    if ans[m]>ans[m-1]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

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

for i in range(k,n):
    if a[i]>a[i-k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import sys
N = int(input())


def query(num):
    print(num)
    return int(input())


result = [-1] * (N + 1)
result[0] = query(0)
result[N] = result[0]
edge = [0, N]
if result[0] == "Vacant":
    sys.stdout.flush()
else:
    for i in range(30):
        idx = int(abs(edge[0] - edge[1]) / 2) + min(edge)
        result[idx] = query(idx)
        if result[idx] == "Vacant":
            sys.stdout.flush()
            break
        for i in range(2):
            r = result[edge[i]]
            if abs(edge[i] - idx) % 2 == 0:
                if r != result[idx]:
                    if i == 0:
                        edge[1] = idx
                        break
                    else:
                        edge[0] = idx
                        break
            elif abs(edge[i] - idx) % 2 == 1:
                if r == result[idx]:
                    if i == 0:
                        edge[1] = idx
                        break
                    else:
                        edge[0] = idx
                        break
    sys.stdout.flush()


### FIXED CODE ###

import sys
N = int(input())


def query(num):
    print(num)
    return input()


result = [-1] * (N + 1)
result[0] = query(0)
result[N] = result[0]
edge = [0, N]
if result[0] == "Vacant":
    sys.stdout.flush()
else:
    for i in range(30):
        idx = int(abs(edge[0] - edge[1]) / 2) + min(edge)
        result[idx] = query(idx)
        if result[idx] == "Vacant":
            sys.stdout.flush()
            break
        for i in range(2):
            r = result[edge[i]]
            if abs(edge[i] - idx) % 2 == 0:
                if r != result[idx]:
                    if i == 0:
                        edge[1] = idx
                        break
                    else:
                        edge[0] = idx
                        break
            elif abs(edge[i] - idx) % 2 == 1:
                if r == result[idx]:
                    if i == 0:
                        edge[1] = idx
                        break
                    else:
                        edge[0] = idx
                        break
    sys.stdout.flush()
### BUGGY CODE ###

N = int(input())
ok = False

for i in range(1, 3501):
    for j in range(1, 3501):
        if (4/N - 1/i - 1/j) > 0 and (4/N - 1/i - 1/j)**-1 == int((4/N - 1/i - 1/j)**-1) and int((4/N - 1/i - 1/j)**-1) <= 3500:
            print(i, j, int((4/N - 1/i - 1/j)**-1))
            ok = True
            break
    if ok:
        break

### FIXED CODE ###

N = int(input())
ok = False

for i in range(1, 3501):
    for j in range(1, 3501):
        if N*(i+j) < 4*i*j:
            w = 1 / (4/N - 1/i - 1/j)
            if abs(int(w)-w) < 10**-7:
                print(i, j, int(w))
                ok = True
                break
    if ok:
        break
### BUGGY CODE ###

N = int(input())
Alist = []
Blist = []
sumlist = []

for i in range(N):
    a,b = map(int,input().split())
    Alist.append(a)
    Blist.append(b)
    sumlist.append(a+b)

counter = 0
takahasi = 0
aoki = 0
for i in range(N):
    if counter == 0:
        index = sumlist.index(max(sumlist))
        takahasi += Alist[index]
        sumlist[index] = 0
        counter = 1
        continue
    if counter == 1:
        index = sumlist.index(max(sumlist))
        aoki += Blist[index]
        sumlist[index] = 0
        counter = 0
        continue

print(takahasi-aoki)


### FIXED CODE ###

import numpy as np

N = int(input())
Alist = []
Blist = []
sumlist = []

for i in range(N):
    a,b = map(int,input().split())
    Alist.append(a)
    Blist.append(b)
    sumlist.append(a+b)

index = np.argsort(sumlist)

sumlist = np.sort(sumlist)




counter = 0
takahasi = 0
aoki = 0

for i in range(N)[::-1]:
    if counter == 0:
        takahasi += Alist[index[i]]
        counter = 1
        continue
    if counter == 1:
        aoki += Blist[index[i]]
        counter = 0
        continue

print(takahasi-aoki)
### BUGGY CODE ###

N = int(input())
X = 0
C = 0

for s in input():
    X <<= 1
    if s == '1':
        X += 1
        C += 1

def f(n, c):
    if n == 0:
        return 0
    n %= c

    ret = 1
    while n > 0:
        n %= bin(n).count('1')
        ret += 1
    return ret

ans = [f(X ^ (1 << i), C + (1 if (X & (1 << i) == 0) else -1)) for i in range(N)]
print(*ans[::-1], sep='\n')


### FIXED CODE ###

N = int(input())
X = input()

cnt = X.count('1')
if cnt == 1:
    for x in X[:-1]:
        if x == '0':
            print(1)
        else:
            print(0)
    if X[-1] == '1':
        print(0)
    else:
        print(2)
    exit()

M = 0
for x in X:
    M <<= 1
    if x == '1':
        M += 1

def solve(n):
    ret = 1
    while n > 0:
        ret += 1
        n %= bin(n).count('1')
    return ret

ans = []
p = M % (cnt + 1)
m = M % (cnt - 1)

for i in range(N):
    if X[i] == '0':
        ans.append(solve((p + pow(2, N - i - 1, cnt + 1)) % (cnt + 1)))
    else:
        ans.append(solve((m - pow(2, N - i - 1, cnt - 1)) % (cnt - 1)))
print(*ans, sep='\n')
### BUGGY 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

Q = int(input())
lr_list = [list(map(int,input().split())) for _ in range(Q)]
flags = [0] * (10 ** 5)


for l, r in lr_list:
    ans = 0
    for i in range(l, r + 1, 2):
        if flags[i] == -1:
            continue
        elif flags[i] == 0:
            flag1 = is_prime(i)
            flag2 = is_prime((i + 1) // 2)
            if flag1 and flag2:
                flags[i] = 1
            else:
                flags[i] = -1
        if flags[i] == 1:
            ans += 1
    print(ans)

### FIXED CODE ###

import math
import bisect
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

Q = int(input())
lr_list = [list(map(int,input().split())) for _ in range(Q)]
flags = [False] * (10 ** 5)


for i in range(1, 10 ** 5 + 1, 2):
    if not flags[i]:
        flag1 = is_prime(i)
        flag2 = is_prime((i + 1) // 2)
        if flag1 and flag2:
            flags[i] = True
True_idxs = []
for i in range(len(flags)):
    if flags[i]:
        True_idxs.append(i)

# print(True_idxs)

for l, r in lr_list:
    l_idx = bisect.bisect_left(True_idxs, l)
    r_idx = bisect.bisect_right(True_idxs, r)
    print(r_idx - l_idx)
### BUGGY CODE ###

import math

n = int(input())
l0 = list(map(int, input().split()))
mini = math.factorial(max(l0))
maxii = 0
for i in l0:
    if i != max(l0) and math.factorial(max(l0)-i)*math.factorial(i) < mini:
        mini = math.factorial(max(l0)-i)*math.factorial(i)
        maxii = i

print(max(l0), maxii)

### FIXED CODE ###

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

l0 = sorted(l0)
m = l0.pop()

mini = m + 1
maxii = 0
ans = 0
for i in range(len(l0)):
    if l0[i] < m/2:
        ipred = l0[i]
        continue
    if abs((m/2 - l0[i-1])) >= abs((m/2 - l0[i])):
        ans = m, l0[i]
    else:
        ans = m, l0[i-1]
    break

if not ans:
    print(m, ipred)
else:
    for i in ans:
        print(i, end=' ')
### BUGGY CODE ###

n, w = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(n)]
p.insert(0, [0, 0])
dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, w + 1):
        if j >= p[i][0]:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - p[i][0]] + p[i][1])
        else:
            dp[i][j] = dp[i - 1][j]
print(dp[n][w])

### FIXED CODE ###

n, w = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(n)]
p.insert(0, [0, 0])
dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, w + 1):
        if j >= p[i][0]:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - p[i][0]] + p[i][1])
        else:
            dp[i][j] = dp[i - 1][j]
print(dp[n][w])
### BUGGY CODE ###

n = int(input())
s = list(input())
q = int(input())


for _ in range(q):
    cmd, x, y = input().split()
    if cmd == '1':
        s[int(x)-1] = y
    else:
        print(len(set(s[int(x)-1:int(y)])))

### FIXED CODE ###

n = int(input())
s = input()
table = {x: 2**i for i, x in enumerate(map(chr, range(97, 123)))}

SEG_LEN = n
SEG = [0]*(SEG_LEN*2)


def update(i, x):
    i += SEG_LEN
    SEG[i] = table[x]
    while i > 0:
        i //= 2
        SEG[i] = SEG[i*2] | SEG[i*2+1]


def find(left, right):
    left += SEG_LEN
    right += SEG_LEN
    ans = 0
    while left < right:
        if left % 2 == 1:
            ans = SEG[left] | ans
            left += 1
        left //= 2
        if right % 2 == 1:
            ans = SEG[right-1] | ans
            right -= 1
        right //= 2
    return format(ans, 'b').count('1')


for i, c in enumerate(s):
    update(i, c)

q = int(input())
for _ in range(q):
    com, *query = input().split()
    if com == '1':
        idx, x = query
        update(int(idx)-1, x)
    else:
        L, R = map(int, query)
        print(find(L-1, R))
### BUGGY CODE ###

X = int(input())
Acount = 0
Bcount = 0
di= {}
def func(i):
    return i**5
for i in range(10000):
    di[str(func(i))] = str(i)
preA = int(X **(1/5))
while True:
    funcA = preA**5
    if funcA-X>=0 and str(funcA-X) in di.keys():
        print(str(preA)+" "+di[str(funcA-X)])
        break
    elif X-funcA>= 0 and str(X-funcA) in di.keys():
        print(str(preA)+" -"+di[str(X-funcA)])
        break
    preA += 1

### FIXED CODE ###

X = int(input())
Acount = 0
Bcount = 0
di= {}
def func(i):
    return i**5
for i in range(5000):
    di[str(func(i))] = str(i)
preA = int(X **(1/5))-1000
while True:
    funcA = preA**5
    if funcA-X>=0 and str(funcA-X) in di.keys():
        print(str(preA)+" "+di[str(funcA-X)])
        break
    elif X-funcA>= 0 and str(X-funcA) in di.keys():
        print(str(preA)+" -"+di[str(X-funcA)])
        break
    preA += 1
### BUGGY CODE ###

n = int(input())
list_a = list(map(int, input().split()))
list_memo = []
for i in range(0,n):
    if i == 0:
        list_memo.append(list_a[i])
    else:
        list_memo.append(list_a[i]-list_a[i-1])
list_memo.append(-list_a[n-1])

for i in range(0,n):
    ans = 0
    for j in range(0,n+1):
        if j != i and j != i + 1:
            ans += abs(list_memo[j])
    ans += abs(list_memo[i+1] + list_memo[i])
    print(ans)


### FIXED CODE ###

n = int(input())
list_a = list(map(int, input().split()))
list_memo = []
for i in range(0,n):
    if i == 0:
        list_memo.append(list_a[i])
    else:
        list_memo.append(list_a[i]-list_a[i-1])
list_memo.append(-list_a[n-1])
ans_pre = 0
for i in range(0,n+1):
    ans_pre += abs(list_memo[i])
for i in range(0,n):
    ans = ans_pre - abs(list_memo[i]) - abs(list_memo[i+1]) + abs(list_memo[i] + list_memo[i+1])
    print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
A = LIST()

MAX = N * K
# dp[i][j][k] := i枚目までからj枚取って、合計をkにする通り数
dp = list3d(N+1, N+1, MAX+1, 0)
dp[0][0][0] = 1
for i in range(N):
    a = A[i]
    for j in range(i+1):
        for k in range(MAX+1):
            dp[i+1][j][k] += dp[i][j][k]
            if j+1 <= N and k+a <= MAX:
                dp[i+1][j+1][k+a] += dp[i][j][k]
ans = 0
for j in range(1, N+1):
    # 1枚以上取った時の、平均がKになる所 → j枚取って合計がj*Kの所 を合計する
    ans += dp[N][j][j*K]
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

""" 3次元DP """

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

# i(=xNリストからどこまでを選べる範囲とするか)からj(=0～N)枚選んで、選んだ値の合計をkにするような選び方の総数
dp = [[[0] * (N*X+1) for j in range(N+1)] for i in range(N+1)]
dp[0][0][0] = 1

ans = 0
for i in range(1,N+1):
    for j in range(N+1):
        for k in range(N*X+1):
            # 求めたい合計(k)が、この周回で増えた選択肢(xN[i-1])より小さい場合、
            # 選び方の総数は増える見込みがないので前回の値をそのまま使用
            if k < xN[i-1]:
                dp[i][j][k] = dp[i-1][j][k]
            # 合計kが大きければ、増やせるかもしれないので、選んだ数と合計を減らしたところを見に行く
            # 選べる数j=0は論外だし、添え字[j-1]に良くないので条件で除外する
            elif k >= xN[i-1] and j > 0:
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-xN[i-1]]
            # 選んだ数と合計から判断して、平均が条件に合うものなら答えに足す
            if i == N and j > 0 and k == j*A:
                ans += dp[i][j][k]

# ans = 0
# for k in range(1,N+1):
#     ans += dp[N][k][k*A]
        
print(ans)
### BUGGY CODE ###

from collections import deque
import sys
input=sys.stdin.readline
inf=float("inf")


def BFS():
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque()
    queue.append([Cx-1,Cy-1,0])
    D[Cx-1][Cy-1]=0

    while len(queue)>0:
        x,y,cnt=queue.popleft()
        for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
            X,Y=x+i,y+j
            if 0<=X<h and 0<=Y<w:
                if S[X][Y]=="." and D[X][Y]>cnt:
                    D[X][Y]=cnt
                    queue.append([X,Y,cnt])

        for X in range(max(0,x-2),min(h,x+3)):
            for Y in range(max(0,y-2),min(w,y+3)):
                if S[X][Y]=="." and D[X][Y]>cnt+1:
                    D[X][Y]=cnt+1
                    queue.append([X,Y,cnt+1])

    return D[Dx-1][Dy-1]


h,w=map(int,input().split())
Cx,Cy=map(int,input().split())
Dx,Dy=map(int,input().split())
S=[list(input()) for _ in range(h)]

D=BFS()
print(D if D!=inf else -1)

### FIXED CODE ###

from collections import deque
import sys
input=sys.stdin.readline
inf=float("inf")


def BFS():
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque()
    queue.append([Cx-1,Cy-1,0])
    D[Cx-1][Cy-1]=0

    while len(queue)>0:
        x,y,cnt=queue.popleft()
        for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
            X,Y=x+i,y+j
            if 0<=X<h and 0<=Y<w:
                if S[X][Y]=="." and D[X][Y]>cnt:
                    D[X][Y]=cnt
                    queue.appendleft([X,Y,cnt])

        for X in range(max(0,x-2),min(h,x+3)):
            for Y in range(max(0,y-2),min(w,y+3)):
                if S[X][Y]=="." and D[X][Y]>cnt+1:
                    D[X][Y]=cnt+1
                    queue.append([X,Y,cnt+1])

    return D[Dx-1][Dy-1]


h,w=map(int,input().split())
Cx,Cy=map(int,input().split())
Dx,Dy=map(int,input().split())
S=[list(input()) for _ in range(h)]

D=BFS()
print(D if D!=inf else -1)
### BUGGY CODE ###

N=int(input())
i,j=1,1
C=[(i,j)]
while True:
    p=C.pop(0)
    if p[0]*p[1]==N:
      print(p[0]+p[1]-2)
      break
    else:
      C.append((i+1,j))
      C.append((i,j+1))
      i+=1
      j+=1

### FIXED CODE ###

N=int(input())
for i in range(int(N**0.5)+1,0,-1):
  if N%i==0:
    print(int(N/i+i-2))
    exit()
### BUGGY CODE ###

n,m = [int(i) for i in input().split()]
l = [[int(i) for i in input().split()] for _ in range(m)]
l2 = sorted(l,key = lambda x:(x[0],x[1]))
t = [[] for _ in range(n)]

for p,y in l2:
    t[p-1].append(y)
    
for i in l:
    order = t[i[0]-1].index(i[1])
    print(str(i[0]).zfill(6)+str(order+1).zfill(6))


### FIXED CODE ###

from bisect import bisect_left
n,m = [int(i) for i in input().split()]
l = [[int(i) for i in input().split()] for _ in range(m)]
l2 = sorted(l,key = lambda x:(x[0],x[1]))
t = [[] for _ in range(n)]

for p,y in l2:
    t[p-1].append(y)
    
for i in l:
    order = bisect_left(t[i[0]-1],i[1])
    print(str(i[0]).zfill(6)+str(order+1).zfill(6))
### BUGGY CODE ###

import numpy as np
N, *A = map(int, open(0).read().split())
B = np.cumsum(A)
j = 1
a = A[0]
b = A[1]
c = A[2]
d = B[-1]-B[2]
j = 0
h = 2
while h<N:
  if abs(d-c)>abs(d-c-2*A[h+1]):
    h += 1
    c += A[h]
    d -= A[h]
    continue
  break
x = max(a,b,c,d)
y = min(a,b,c,d)
ans = x-y
for i in range(2,N-2):
  b += A[i]
  c -= A[i]
  while j<i:
    if abs(b-a)>abs(b-a-2*A[j+1]):
      j += 1
      a += A[j]
      b -= A[j]
      continue
    break
  while h<N:
    if abs(d-c)>abs(d-c-2*A[h+1]):
      h += 1
      c += A[h]
      d -= A[h]
      continue
    break
  x = max(a,b,c,d)
  y = min(a,b,c,d)
  ans = min(ans,x-y)
print(ans)

### FIXED CODE ###

N, *A = map(int, open(0).read().split())
B = [A[0]]
for i in range(1,N):
  B += [B[-1]+A[i]]
j = 1
a = A[0]
b = A[1]
c = A[2]
d = B[-1]-B[2]
j = 0
h = 2
while h<N:
  if abs(d-c)>abs(d-c-2*A[h+1]):
    h += 1
    c += A[h]
    d -= A[h]
    continue
  break
x = max(a,b,c,d)
y = min(a,b,c,d)
ans = x-y
for i in range(2,N-2):
  b += A[i]
  c -= A[i]
  while j<i:
    if abs(b-a)>abs(b-a-2*A[j+1]):
      j += 1
      a += A[j]
      b -= A[j]
      continue
    break
  while h<N:
    if abs(d-c)>abs(d-c-2*A[h+1]):
      h += 1
      c += A[h]
      d -= A[h]
      continue
    break
  x = max(a,b,c,d)
  y = min(a,b,c,d)
  ans = min(ans,x-y)
print(ans)
### BUGGY CODE ###

s=input()
l=len(s)
amari=[0]*2019
amari[0]=1

d=0

for c in s[::-1]:
    d=(int(c)*10**len(str(d)) + d)
    amari[d%2019]+=1


ans=0
for i in amari:
    ans+=i*(i-1)//2
print(ans)

### FIXED CODE ###

s=input()
l=len(s)
amari=[0]*2019
amari[0]=1

d=0
digi=1

for c in s[::-1]:
    d=(int(c)*digi + d)%2019
    amari[d]+=1
    digi=(digi*10)%2019

ans=0
for i in amari:
    ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from collections import defaultdict
INF = float("inf")
MOD = 10**9+7


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))
        self.E[t].append((f, w))


N = int(input())
c = [x-1 for x in map(int, input().split())]
A = [None]*(N-1)
B = [None]*(N-1)
for i in range(N-1):
    A[i], B[i] = map(int, input().split())

g = Graph(N)
for a, b in zip(A, B):
    g.add_edge(a-1, b-1)

# k=1, 2, ..., Nに対して
# 色kが塗られている頂点を一度以上通るような単純パスの数を求める
# 全パスの個数 - 色kが塗られている頂点を一度も通らない単純パスの数
# 全パスの個数はN*(N+1)/2

# グラフを色kのノードで分割して、部分グラフ内での単純パスの総数を求めれば良い
# 各ノードに状態として辞書をもたせる。
# 辞書は色iを通らずに到達可能な頂点の数を持つ。

# 辞書
reachable = [defaultdict(int) for _ in range(N)]

# 回答用
ans = [0]*N


def f(curr, par=-1):
    # 再帰関数
    # curr: 現在の節点
    # par : 親節点の番号
    for dest, w in g.E[curr]:
        if dest == par:
            continue
        f(dest, curr)

        for color in range(N):
            n = reachable[dest][color]
            if color == c[curr]:
                # 自身の色と同じ場合、子の頂点の数から加算
                ans[color] += n*(n+1)//2
                reachable[curr][color] = 0
            else:
                # 自身の色以外については、子の情報から自分の情報を作る
                reachable[curr][color] += n
    for color in range(N):
        if color != c[curr]:
            reachable[curr][color] += 1
    return


f(0)
for color in range(N):
    if color != c[0]:
        n = reachable[0][color]
        ans[color] += n*(n+1)//2

tot = N*(N+1)//2
for a in ans:
    print(tot-a)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from collections import defaultdict
INF = float("inf")
MOD = 10**9+7


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))
        self.E[t].append((f, w))


N = int(input())
c = [x-1 for x in map(int, input().split())]
A = [None]*(N-1)
B = [None]*(N-1)
for i in range(N-1):
    A[i], B[i] = map(int, input().split())

g = Graph(N)
for a, b in zip(A, B):
    g.add_edge(a-1, b-1)

# k=1, 2, ..., Nに対して
# 色kが塗られている頂点を一度以上通るような単純パスの数を求める
# 全パスの個数 - 色kが塗られている頂点を一度も通らない単純パスの数
# 全パスの個数はN*(N+1)/2

# グラフを色kのノードで分割して、部分グラフ内での単純パスの総数を求めれば良い
# 各ノードに状態として辞書をもたせる。
# x辞書は色iを通らずに到達可能な頂点の数を持つ。
# o辞書は色iを通らずに到達不可能な頂点の数を持つ。

# 回答用
ans = [0]*N


def f(curr, par=-1):
    # 再帰関数
    # curr: 現在の節点
    # par : 親節点の番号
    ret = defaultdict(int)
    size = 1
    for dest, w in g.E[curr]:
        if dest == par:
            continue
        sz, child = f(dest, curr)
        size += sz

        # 自身の色と同じ場合、子の頂点の数から加算
        n = sz-child[c[curr]]
        ans[c[curr]] += n*(n+1)//2

        # マージ
        if len(ret) < len(child):
            child, ret = ret, child
        for key in child:
            ret[key] += child[key]

    ret[c[curr]] = size
    return size, ret


sz, ret = f(0)
for color in range(N):
    if color != c[0]:
        n = sz-ret[color]
        ans[color] += n*(n+1)//2

tot = N*(N+1)//2
for a in ans:
    print(tot-a)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

x = int(input())

def per(year):
  if year == 0:
    return 100
  else:
    return int(per(year-1) * 1.01)
  
year = 0
while True:
  if per(year) >= x:
    print(year)
    break
  else:
    year += 1

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

x = int(input())

def per(year):
  if year == 0:
    return 100
  else:
    return int(per(year-1) * 1.01)
  
year = 0
while True:
  if per(year) >= x:
    print(year)
    break
  else:
    year += 1
### BUGGY CODE ###

from collections import Counter
import copy 
n=int(input())
c=input()
cl=copy.deepcopy(c)
cl=list(cl)
d=Counter(c)
ans=0


if d["R"]==0 or d["W"]==0:
  print(0)
  exit()
swap=0
for i in range(n//2):
  indexes = [j for j, x in enumerate(cl) if x == "R"]
  #print(cl)
  if cl[i]=="W":
    cl[indexes[-1]]="W"
    cl[i]="R"
    swap+=1

#print(cl)
#print(cl[cl.index("W"):])

d=Counter(cl[cl.index("W"):])
ans+=swap+d["R"]
print(ans)

### FIXED CODE ###

from collections import Counter
n=int(input())
c=input()
d=Counter(c)
w,r=Counter(c)["W"], Counter(c)["R"]
ans=0
for i in range(r):
  if c[i]=="W":
    ans+=1

print(ans)