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

# D
from collections import deque
from bisect import bisect_left as bl

f=lambda:map(int,input().split())
N,M=f()
D=[[] for _ in [0]*(N+1)]
F=[0]*(N+1)
F[0]=1
for _ in range(M):
    a,b=f()
    if not b in D[a]:
        D[a].append(b)
    if not a in D[b]:
        D[b].append(a)

q=deque()
res=0
while bl(F,1):
    index=bl(F,1)-1
    q.append(index)
    tmp=0
    while q:
        k=q.pop()
        if F[k]!=1:
            tmp+=1
            F[k]=1
            for d in D[k]:
                if F[d]!=1:
                    q.append(d)
            D[k]=0
    res=max(res,tmp)

print(res)

### FIXED CODE ###

# D
from collections import deque
from bisect import bisect_left as bl

f=lambda:map(int,input().split())
N,M=f()
D=[[] for _ in [0]*(N+1)]
F=[0]*(N+1)
F[0]=1
for _ in range(M):
    a,b=f()
    D[a].append(b)
    D[b].append(a)

q=deque()
res=0


while bl(F,1):
    index=bl(F,1)-1
    q.append(index)
    tmp=0
    while q:
        k=q.pop()
        if F[k]!=1:
            tmp+=1
            F[k]=1
            for d in list(set(D[k])):
                if F[d]!=1:
                    q.append(d)
            D[k]=0
    res=max(res,tmp)

print(res)
### BUGGY CODE ###

#https://atcoder.jp/contests/dp/tasks/dp_f
#2019-01-14
s = input()
t = input()

def LCS(S,T):
  #初期化
  dp = [["" for i in range(len(T)+1)] for j in range(len(S)+1)]

  #DP
  for i in range(len(S)):
    for j in range(len(T)):
      dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j], key=len)
      if S[i]==T[j]:
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+S[i], key=len)
  return dp[len(S)][len(T)]

print(LCS(s,t))

### FIXED CODE ###

#https://atcoder.jp/contests/dp/tasks/dp_f
#2019-01-14
S = input()
T = input()

#初期化
dp = [[0 for i in range(len(T)+1)] for j in range(len(S)+1)]

#DP
for i in range(len(S)):
    for j in range(len(T)):
        dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j], dp[i][j] + (S[i] == T[j]))

st = []

x = len(S)
y = len(T)
while x > 0 and y > 0:
    if dp[x][y] == dp[x-1][y]: x -= 1
    elif dp[x][y] == dp[x][y-1]: y -= 1
    else: 
        x -= 1
        y -= 1
        st += S[x]
print("".join(reversed(st)))
### BUGGY CODE ###

N = int(input())

tmp = []
counter = 0
for i in range(N):
    new_str = ''.join(sorted(str(input())))
    
    if i != 0:
        counter += tmp.count(new_str)
    tmp.append(new_str)

#new_str_list = [i for i in new_str = ''.join(list(sorted(str(input()))))]
#print(new_str_list)

    #for j in range(i):
    #    if str(new_str) == str(tmp[j]):
    #        counter += 1

print(counter)

### FIXED CODE ###

N = int(input())

tmp = []
counter = 0
for i in range(N):
    new_str = ''.join(sorted(str(input())))
    
    #if i != 0:
    #    counter += tmp.count(new_str)
    tmp.append(new_str)

import collections
c = collections.Counter(tmp)

#new_str_list = [i for i in new_str = ''.join(list(sorted(str(input()))))]
#print(new_str_list)

    #for j in range(i):
    #    if str(new_str) == str(tmp[j]):
    #        counter += 1
value = list(c.values())
#print(value)

for j in value:
    for k in range(j):
        counter += k

print(counter)
### BUGGY CODE ###

N = int(input())
A = [int(v) for v in input().split()]

def gcd(v1, v2):
    if v2 == 0:
        return v1
    return gcd(v2, v1 % v2)

a1 = A[0]

for a2 in A[1:]:
    a3 = gcd(a1, a2)
    a1 = a1 * a2 // a3

#print(a1)

v = a1
total = 0
for a in A:
    total += v // a 
    total %= 1000000007
    #while total > 1000000007:
    #total -= 1000000007

print(total)

### FIXED CODE ###

N = int(input())
A = [int(v) for v in input().split()]

def gcd(v1, v2):
    if v2 == 0:
        return v1
    return gcd(v2, v1 % v2)

A.sort()
a1 = A[0]

for a2 in A[1:]:
    a3 = gcd(a1, a2)
    a1 = a1 * a2 // a3

v = a1
total = 0
for a in A:
    total += v // a 
#    while total > 1000000007:
#        total -= 1000000007

total %= 1000000007
print(total)
### BUGGY CODE ###

def Get_nC2(n):
    return int(n*(n-1) / 2);


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

all_cnt = 0
num_cnt_dict = {}
comb_cnt_dict = {}
for i in range(min(A_i), max(A_i)+1):
    if i in A_i and A_i.count(i) > 1:
        num_cnt_dict[i] = A_i.count(i)
        all_cnt += Get_nC2(num_cnt_dict[i])

for a_i in A_i:
    if a_i in comb_cnt_dict:
        print(comb_cnt_dict[a_i])
    elif a_i in num_cnt_dict:
        comb_cnt_dict[a_i] = all_cnt - Get_nC2(num_cnt_dict[a_i]) + Get_nC2(num_cnt_dict[a_i]-1)
        print(comb_cnt_dict[a_i])
    else:
        print(0)


### FIXED CODE ###

from collections import Counter

def Get_nC2(n):
    return int(n*(n-1) / 2)


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

c = Counter(A_i)


total = sum(list(map(Get_nC2, c.values())))

for a_i in A_i:
    result =  total - Get_nC2(c[a_i]) + Get_nC2(c[a_i]-1)
    print(result)
### BUGGY CODE ###

l,r=map(int,input().split())
an=(l*(l+1))%2019

for i in range(l,r):
    for j in range(i+1,r+1):
        if (i*j)%2019 < an:
            an=(i*j)%2019

print(an)

### FIXED CODE ###

l,r=map(int,input().split())
an=(l*(l+1))%2019

for i in range(l,r):
    for j in range(i+1,r+1):
        if (i*j)%2019 < an:
            an=(i*j)%2019
        if an==0:
            print("0")
            exit()

print(an)
### BUGGY CODE ###

import collections

inp = [input() for i in range(2)]
N = int(inp[0])
A = inp[1].split()
A = [int(i) for i in A]
B = 0
for k in A:
    a = A.count(k)
    B += (a - 1) / 2

for k in range(N):
    # counter = 0
    # other = A[:k] + A[k+1:]
    # for i in range(N-1):
    #     counter += other.count(other[i])
    #     counter -= 1
    c = A.count(A[k]) - 1
    counter = B - c
    print(int(counter))


### FIXED CODE ###

import math
inp = [input() for i in range(2)]
N = int(inp[0])
A = list(map(int, inp[1].split()))
# B = 0
d = {}
for k in A:
    # a = A.count(k)
    # B += (a - 1) / 2
    if k in d.keys():
        d[k] += 1
    else:
        d[k] = 1

# for k in range(N):
#     c = A.count(A[k]) - 1
#     counter = B - c
#     print(int(counter))

p = {}
for k in d.keys():
    cnt = d[k]
    p[k] = cnt * (cnt-1) / 2

total = sum(p.values())

for item in A:
    print(int(total - d[item] + 1))
### BUGGY CODE ###

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

A_sum = [0] * (N + 1)
for i in range(1, N+1):
    A_sum[i] = A_sum[i-1] + A[i-1]
dict = {}
for a in A_sum:
    if a in dict.keys():
        dict[a] = dict[a] + 1
    else:
        dict[a] = 1
ans = 0
for num in dict.values():
    ans += num * (num-1) / 2
print(int(ans))


### FIXED CODE ###

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

A_sum = [0] * (N + 1)
for i in range(1, N+1):
    A_sum[i] = A_sum[i-1] + A[i-1]
A_sum.sort()

ans = 0
add = 0
a_cur = float('inf')
for a in A_sum:
    if a != a_cur:
        add = 0
        a_cur = a
    else:
        add += 1
        ans += add
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))

now = 1
path = [1]
cnt = 1


i = 0
while i < min(N + 2, K):
    now = A[now]
    i += 1
    if now in path: break
    path.append(now)

if i == K:
    print(now)
    quit()

lo_start = path.index(now)
lo_len = i - lo_start
loop = path[lo_start:]

print(loop[(K - lo_start) % lo_len])

### FIXED CODE ###

N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))

now = 1
path = [1]

for i in range(N + 2):
    now = A[now]
    path.append(now)

if i >= K:
    print(path[K])
    quit()

now = path.pop()
lo_start = i - 1
while path[lo_start] != now:
    lo_start -= 1

loop = path[lo_start:]

ans = loop[(K - path.index(now)) % len(loop)]

print(ans)
### BUGGY CODE ###

from operator import mul
from functools import reduce

def ConZ(i):
    z_num = i+int(i*(i-1)/2)
    return z_num
#def ConN(i):
    #n_num = int(i*(i-1)/2)
    #return n_num

def cmb(n):
    over = reduce(mul, range(n, n - 2, -1))
    under = reduce(mul, range(1,2 + 1))
    return over // under


S = input()[::-1]
keta = 1
A_num = 0
x = 0
mod = [0]*2019
for i in range(len(S)):
    A_num += (int(S[i:i+1])*keta)%2019
    if A_num >= 2019:
        A_num = A_num%2019
    mod[A_num] +=1
    keta*=10
    
#print(mod[0])
x += ConZ(mod[0])
del mod[0]

for j in range(len(mod)):
    x+=cmb(mod[j])
print(x)


### FIXED CODE ###

from operator import mul
from functools import reduce
import numpy as np
#def ConZ(i):
    #z_num = i+int(i*(i-1)/2)
    #return z_num
#def ConN(i):
    #n_num = int(i*(i-1)/2)
    #return n_num

def cmb(n):
    over = reduce(mul, range(n, n - 2, -1))
    under = reduce(mul, range(1,2 + 1))
    return over // under


S = input()[::-1]
keta = 1
A_num = 0
x = 0
mod = np.array([0]*2019)
mod[0] += 1
for i in range(len(S)):
    A_num += (int(S[i:i+1])*keta)%2019
    if A_num >= 2019:
        A_num = A_num%2019
    mod[A_num] +=1
    #keta*=10
    keta = keta * 10 % 2019
#print(mod)
#x += ConZ(mod[0])
#del mod[0]

#for j in range(len(mod)):
    #x+=cmb(mod[j])
#print(x)
print(int(np.sum(mod* (mod - 1) /2)))
### BUGGY CODE ###

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

dist = [-1] * (N+1)
dist[1] = 0
connection = [[] for _ in range(N+1)]
ans = [-1] * (N+1)

for quel in range(M):
    a, b = map(int, input().split())
    connection[a].append(b)
    connection[b].append(a)

que = []
que.append(1)

while que:
    v = que.pop(0)

    for i in connection[v]:
        if dist[i] != -1:continue

        dist[i] = dist[v] + 1
        que.append(i)
        ans[i] = v

#print(dist)
print('Yes')
for j in range(2, N+1):
    print(ans[j])

### FIXED CODE ###

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

dist = [-1] * (N+1)
dist[1] = 0
connection = [[] for _ in range(N+1)]
ans = [-1] * (N+1)

for quel in range(M):
    a, b = map(int, input().split())
    connection[a].append(b)
    connection[b].append(a)

que = []
que.append(1)

while que:
    v = que.pop(0)

    for i in connection[v]:
        if dist[i] != -1:continue

        dist[i] = dist[v] + 1
        que.append(i)
        ans[i] = v

#print(dist)
print('Yes')
for j in range(2, N+1):
    print(ans[j])
### BUGGY CODE ###

#https://tjkendev.github.io/procon-library/python/range_query/rmq_segment_tree.html
# N: 処理する区間の長さ

# 中身は追えてない
#bit管理,26個作るより速いだろう
#演算はor

N = int(input())
s = input()


N0 = 2**(N-1).bit_length()
INF = 0
data = [0]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = 1<<x
    while k >= 0:
        k = (k - 1) // 2
        data[k] =data[2*k+1]|data[2*k+2]
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = s|data[R-1]

        if L & 1:
            s = s|data[L-1]
            L += 1
        L >>= 1; R >>= 1
    return s

for i in range(N):
    update(i,ord(s[i])-ord("a"))
q = int(input())
for j in range(q):
    t,l,r = input().split( )
    if t=="1":
        update(int(l)-1,ord(r)-ord("a"))
        
    else:
        bit = bin(query(int(l)-1,int(r)))[2:]
        ans = 0
        for i in bit:
            ans += int(i)
        print(ans)
        

### FIXED CODE ###

#https://tjkendev.github.io/procon-library/python/range_query/rmq_segment_tree.html
# N: 処理する区間の長さ

#bit管理
#演算はor
N = int(input())
s = input()


N0 = 1
while N0<=N:
    N0*=2
INF = 0
data = [0]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = 1<<x
    while k >= 0:
        k = (k - 1) // 2
        data[k] =data[2*k+1]|data[2*k+2]
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = s|data[R-1]

        if L & 1:
            s = s|data[L-1]
            L += 1
        L >>= 1; R >>= 1
    return s

for i in range(N):
    update(i,ord(s[i])-ord("a"))
q = int(input())

for j in range(q):
    t,l,r = input().split( )
    if t=="1":
        update(int(l)-1,ord(r)-ord("a"))
        
    else:
        bit = bin(query(int(l)-1,int(r)))[2:]
        ans = 0
        for i in bit:
            ans += int(i)
        print(ans)
### BUGGY CODE ###

def main():
    n, m = map(int, input().split())
    w = [0] * n
    v = [0] * n
    for i in range(n):
        wt, vt = list(map(int, input().split()))
        w[i] = wt
        v[i] = vt
    l = [[0] * (m + 1) for _ in range(n)]
    for i in range(n):
        for j in range(m+1):
            if j - w[i] >= 0:
                l[i][j] = max(v[i] + l[i-1][j-w[i]], l[i-1][j])
            else:
                l[i][j] = l[i-1][j]
    print(l[-1][-1])
main()


### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    w = [0] * n
    v = [0] * n
    for i in range(n):
        w[i], v[i] = list(map(int, input().split()))
    l = [0] * (m + 1)
    for i in range(n):
        for j in range(m, w[i] - 1, -1):
            x = v[i] + l[j-w[i]]
            if x > l[j]:
                l[j] = x
    print(l[-1])
main()
### BUGGY CODE ###

s = input()
t = input()
S,T = len(s),len(t)
dp = [['']*(T+1) for _ in range(S+1)]
for i in range(S):
    for j in range(T):
        if s[i]==t[j]:
            dp[i+1][j+1] = dp[i][j] + s[i]
        else:
            if len(dp[i+1][j]) >= len(dp[i][j+1]):
                dp[i+1][j+1] = dp[i+1][j]
            else:
                dp[i+1][j+1] = dp[i][j+1]
print(dp[-1][-1])

### FIXED CODE ###

s = input()
t = input()
S,T = len(s),len(t)
dp = [[0]*(T+1) for _ in range(S+1)]
for i in range(S):
    for j in range(T):
        if s[i]==t[j]:
            dp[i+1][j+1] = 1 + dp[i][j]
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
ans = ''
i,j = S,T
while dp[i][j]:
    if dp[i][j] ==dp[i][j-1]:
        j-=1
    elif dp[i][j] == dp[i-1][j]:
        i-=1
    else:
        ans = s[i-1] + ans
        i-=1
        j-=1
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = float('inf')
from heapq import heapify, heappop, heappush
import collections
import bisect

def main():
    n = int(input())
    mod = 10**9+7

    ans = 1
    for i in range(n):
        ans *= i+1
    print(ans%mod)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = float('inf')
from heapq import heapify, heappop, heappush
import collections
import bisect

def main():
    n = int(input())
    mod = 10**9+7

    ans = 1
    for i in range(n):
        ans *= i+1
        ans %= mod
    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

a=int(input()) # N
b=input().split(" ") # A
c=int(input()) # Q

final=[]
for i in range(c):
    t=0 # total
    d=input().split(" ")
    for i in range(len(b)):
        if int(d[0]) == int(b[i]): # replace
            b[i]=d[1]
        t+=int(b[i]) #sum
    final.append(t)
for j in range(c): # print result
    print (final[j])

### FIXED CODE ###

# collect input N integers
# replace every element whose value is Bi with Ci
# get input x and y and compute them to display output 
from collections import Counter
n=input()
a=list(map(int,input().split()))
b=Counter(a)
n=int(input())
ans=sum(a)
for i in range(n):
    x,y=map(int,input().split())
    ans+=b[x]*(y-x)
    print(ans)
    b[y]+=b[x]
    b[x]=0
### BUGGY CODE ###


S = input()

MOD = 10 ** 9 + 7
count = 0
S_len = len(S)

dp = [[0 for i in range(13)] for j in range(100006)]
c = -1
if S[0] != '?':
    c = int(S[0])
for j in range(10):
    if c == -1:
        dp[1][j] = 1
    else:
        dp[1][c] = 1

for i in range(2, S_len + 1):
    c = -1
    if S[i - 1] != '?':
        c = int(S[i - 1])

    for j in range(13):
        if c == -1:
            for k in range(10):
                dp[i][(j * 10 + k) % 13] += dp[i - 1][j]
        else:
            dp[i][(j * 10 + c) % 13] += dp[i - 1][j]

    for j in range(10):
        dp[i][j] %= MOD

print(dp[S_len][5])




### FIXED CODE ###


S = input()

MOD = 10 ** 9 + 7
count = 0
S_len = len(S)

dp = [[0 for i in range(13)] for j in range(100006)]
c = -1
if S[0] != '?':
    c = int(S[0])
for j in range(10):
    if c == -1:
        dp[1][j] = 1
    else:
        dp[1][c] = 1

for i in range(2, S_len + 1):
    c = -1
    if S[i - 1] != '?':
        c = ord(S[i - 1]) - ord('0')

    for j in range(10):
        if c != -1 and c != j:
            continue
        for k in range(13):
            dp[i][(k * 10 + j) % 13] += dp[i - 1][k] % MOD


print(dp[S_len][5] % MOD)
### BUGGY CODE ###

n = int(input())
s = input()
sum = 0
for i in range(n):
    for j in range(n):
        if i < j:
            for k in range(n):
                if j < k and s[i]!=s[j]:
                    if j-i!=k-j and s[j]!=s[k] and s[k]!=s[i]:
                        sum += 1
print(sum)

### FIXED CODE ###

n = int(input())
s = input()
r = s.count('R')
g = s.count('G')
b = s.count('B')

cnt = r*g*b

for i in range(n):
    j = 1
    while i+2*j < n:
        if s[i] != s[i+j] and s[i+j] != s[i+2*j] and s[i+2*j] != s[i]:
            cnt -= 1
            j += 1
        else:
            j += 1
print(cnt)
### BUGGY CODE ###

from collections import deque
n,x,y = [int(x) for x in input().split()]
l = [[] for i in range(n+1)]
p = []
q = []
l[1].append(2)
for i in range(2,n):
    l[i].append(i+1)
    l[i].append(i-1)
l[n].append(n-1)
l[x].append(y)
l[y].append(x)
clist = [0]*(n+1)
#ここまでで、グラフが隣接リスト表記で表される
for i in range(1,n+1):
    d = deque()
    dist = [-1]*(n+1)
    dist[i] = 0
    d.append(i)
    while True:
        v = d.popleft()
        for i in l[v]:
            if dist[i] != -1:
                continue
            dist[i] = dist[v] + 1
            d.append(i)
        if not d:
            break
    for j in dist:
        if j == -1:
            continue
        clist[j] += 1
for i in range(1,n):
    print((clist[i])//2)

### FIXED CODE ###

n,x,y = [int(x) for x in input().split()]
count = [0]*(n+1)
for i in range(1,n):
    for j in range(i+1,n+1):
        if i < x and j <= x:
            nagasa = j - i
        elif i < x and x < j and j < y:
            nagasa = x-i + min(j-x,y-j+1)
        elif i < x and y <= j:
            nagasa = x-i + j - y + 1
        elif x <= i and i < y and j <= y:
            nagasa = min(j-i,i-x+y-j+1)
        elif x <= i and i < y and y < j:
            nagasa = j - y + min(y-i,i-x+1)
        elif y <= i:
            nagasa = j -i
        count[nagasa] += 1
for i in range(1,n):
    print(count[i])
### BUGGY CODE ###

from collections import deque

n,k=map(int,input().split())
visited=[False]*n
color=[0]*n
visited[0]=True
color[0]=k
mod=10**9+7

graph=[[] for i in range(n)]

for i in range(n-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)


Q=deque()
Q.append((0))

while Q:
  p=Q.pop()
  visited[p]=True
  ans=k
  for i in graph[p]:
      if visited[i]==False:
          Q.append((i))
      
      else:
          ans-=1

          for j in graph[i]:
            if j==p:
              continue
            if visited[j]:
              ans-=1
    
  color[p]=ans


ans=1

for i in color:
    ans*=i
    ans%=mod


print(ans)

### FIXED CODE ###

from collections import deque

n,k=map(int,input().split())
visited=[False]*n
visited[0]=True
color=[0]*n
color[0]=k
mod=10**9+7

graph=[[] for i in range(n)]

for i in range(n-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)


Q=deque()
Q.append((0))
ans=k

while Q:
  p=Q.pop()
  cnt=0
  for i in graph[p]:
    if visited[i]==False:
        cnt+=1
        Q.append((i))
        visited[i]=True

  if p==0:
      for i in range(cnt):
          ans*=k-i-1
          ans%=mod

  else:
      for i in range(cnt):
          ans*=k-i-2
          ans%=mod


print(ans%mod)
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    A = [0] + list(map(int, input().split()))

    for i in range(N):
        A[i + 1] += A[i]

    B = [A[j] - A[i] for i in range(N) for j in range(i + 1, N + 1)]

    ans = 0
    t = 40
    tmp = pow(2, t)
    while t:
        count = 0
        tmp //= 2
        for b in B:
            if ((b & (tmp + ans)) == (tmp + ans)):
                count += 1
            if count >= K:
                ans += tmp
                break
        t -= 1

    print (ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))

for i in range(N):
    A[i + 1] += A[i]

B = [A[j] - A[i] for i in range(N) for j in range(i + 1, N + 1)]

ans = 0
t = 40
while t:
    count = 0
    tmp = pow(2, t -1)
    for b in B:
        if ((b & (tmp + ans)) == (tmp + ans)):
            count += 1
    if count >= K:
        ans += tmp
    t -= 1

print (ans)
### BUGGY CODE ###

from collections import deque, Counter
import sys
H, W = map(int, input().split())
count = 0
grid = ['s' for h in range(H)]
for h in range(H):
    grid[h] = list(input())
    count += Counter(grid[h])['#']

deq = deque([(0, 0)])
visited = [[False for w in range(W)] for h in range(H)]
visited[0][0] = True
route = 0
while deq:
    route += 1
    for _ in range(len(deq)):
        coord = deq.popleft()
        h, w = coord
        visited[h][w] = True
        if coord == (H - 1, W - 1):
            print(H * W - route - count)
            sys.exit()
        if h < H - 1:
            if grid[h + 1][w] != '#' and not visited[h + 1][w]:
                deq.append((h + 1, w))
        if w < W - 1:
            if grid[h][w + 1] != '#' and not visited[h][w + 1]:
                deq.append((h, w + 1))
        if h > 0:
            if grid[h - 1][w] != '#' and not visited[h - 1][w]:
                deq.append((h - 1, w))
        if w > 0:
            if grid[h][w - 1] != '#' and not visited[h][w - 1]:
                deq.append((h, w - 1))

print(-1)




### FIXED CODE ###

from collections import deque, Counter
import sys
H, W = map(int, input().split())
count = 0
grid = ['s' for h in range(H)]
for h in range(H):
    grid[h] = list(input())
    tmp_count = Counter(grid[h])['#']
    if tmp_count == W:
        print(-1)
        sys.exit()
    count += tmp_count

deq = deque([(0, 0)])
visited = [[-1 for w in range(W)] for h in range(H)]
visited[0][0] = 0
route = 0
while deq:
    for _ in range(len(deq)):
        h, w = deq.popleft()
        #print(h, w)
        if (h, w) == (H - 1, W - 1):
            print(H * W - visited[h][w] - 1 - count)
            sys.exit()
        for j, k in ([-1, 0], [0, -1], [0, 1], [1, 0]):
            new_h, new_w = h + j, w + k
            if 0 <= new_h <= H - 1 and 0 <= new_w <= W - 1:
                if grid[new_h][new_w] != '#' and visited[new_h][new_w] == -1:
                    visited[new_h][new_w] = visited[h][w] + 1
                    deq.append((new_h, new_w))
print(-1)
### BUGGY CODE ###

n = int(input())
s = input()

lst = []
for i in range(n):
  lst.append(s[:i].count('W') + s[i+1:].count('E'))
print(min(lst))

### FIXED CODE ###

n = int(input())
s = input()

w_lst = [0] * n
e_lst = [0] * n

for i in range(1, n):
    if s[i - 1] == "W":
        w_lst[i] = w_lst[i - 1] + 1
    else:
        w_lst[i] = w_lst[i - 1]
for i in range(n - 2, -1, -1):
    if s[i + 1] == "E":
        e_lst[i] = e_lst[i + 1] + 1
    else:
        e_lst[i] = e_lst[i + 1]

ans = 10**10
for i in range(n):
    ans = min(ans, w_lst[i] + e_lst[i])
print(ans)