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

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
    
h, w = MAP()
s = [STR() for _ in range(h)]
arr = [[inf for _ in range(w)] for _ in range(h)]
arr[0][0] = 0
que = deque([[0, 0]])
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
while que:
    y, x = map(int, que.popleft())
    if s[y][x] == '.':
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                tmp = arr[y][x]
                arr[y][x] = min(arr[y][x], arr[ny][nx] + 1)
                if arr[ny][nx] >= inf:
                    que.append([ny, nx])
    if y == h - 1 and x == w - 1:
        break
if arr[h - 1][w - 1] >= inf:
    print(-1)
    exit()
ss = 0
for i in range(h):
    ss += s[i].count('.')
print(ss - arr[h - 1][w - 1] - 1)


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

h, w = MAP()
s = [STR() for _ in range(h)]
arr = [[inf for _ in range(w)] for _ in range(h)]
arr[0][0] = 0
que = deque([[0, 0]])
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
while len(que):
    y, x = map(int, que.popleft())
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < h and 0 <= nx < w:
            tmp = arr[y][x]
            arr[y][x] = min(arr[y][x], arr[ny][nx] + 1)
            if arr[ny][nx] >= inf and s[ny][nx] == '.' and not [ny, nx] in que:
                que.append([ny, nx])
    if y == h - 1 and x == w - 1:
        break
if arr[h - 1][w - 1] >= inf:
    print(-1)
    exit()
ss = 0
for i in range(h):
    ss += s[i].count('.')
print(ss - arr[h - 1][w - 1] - 1)
### BUGGY CODE ###

N, K= map(int,input().split())
A = list(map(int,input().split()))
p=0
while p<K:
  B=[0]*(N+1)
  for i in range(N):
    B[max(i-A[i],0)] +=1
    B[min(i+A[i]+1,N)] -=1
  for i in range(N):
    A[i] = sum(B[0:i+1])
  p +=1        
  if min(A)==N:
    break
print(*A)

### FIXED CODE ###

N, K= map(int,input().split())
A = list(map(int,input().split()))
a=A[:]
for _ in range(K):
  B=[0]*(N+1)
  for i in range(N):
    t = a[i]
    B[max(i-t,0)] +=1
    B[min(i+t+1,N)] -=1
  for i in range(N):
    B[i+1] += B[i]
  a=B[:N]        
  if min(a)==N:
    break
print(*a)
### BUGGY CODE ###

import collections

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

roop=0
i=[]
while roop==0 :
    N=abs(N-k)
    i.append(N)
    if collections.Counter(i)["N"] > 2 :
        roop=1

print(min(i))

### FIXED CODE ###

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

print(min(N%k,abs(N%k-k)))
### BUGGY CODE ###

# コードとしては正しいけどTLEが出る
# from collections import Counter
# from math import factorial
# N = int(input())
# A = list(map(int, input().split()))

# Length = len(list(set(A)))

# if (Length == len(A)):
#     for i in range(N):
#         print(0)
#     exit()

# c = Counter(A)
# d = [0] * N
# count = 0
# for i in range(N):
#     if (d[A[i]] != 0):
#         print(d[A[i]])
#         continue

#     if (c[A[i]] == 1):
#         for j, v in c.items():
#             if (v == 1):
#                 continue
#             else:
#                 count += factorial(v) // factorial(2) // factorial(v - 2)
#     else:
#         for j, v in c.items():
#             if (v == 1):
#                 continue
#             elif (j == A[i] and v - 1 != 1):
#                 count += factorial(v - 1) // factorial(2) // factorial(v - 3)
#             elif (j == A[i] and v - 1 == 1):
#                 continue
#             else:
#                 count += factorial(v) // factorial(2) // factorial(v - 2)
#     d[A[i]] = count
#     print(count)
#     count = 0

from collections import Counter
from math import factorial
N = int(input())
A = list(map(int, input().split()))

allCount = 0
c = Counter(A)

for i, v in c.items():
    if (v == 1):
        continue
    else:
        allCount += factorial(v) // factorial(2) // factorial(v - 2)


if (allCount == 0):
    for i in range(N):
        print(0)
    exit()

for i in range(N):
    a = allCount
    num = c[A[i]] - 1
    if (num == 1 or num == 0):
        print(allCount - num)
        continue
    old = factorial(c[A[i]]) // factorial(2) // factorial(c[A[i]] - 2)
    count = factorial(num) // factorial(2) // factorial(num - 2)
    print(a - old + count)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))

allCount = 0
c = Counter(A)

for i, v in c.items():
    if (v == 1):
        continue
    else:
        allCount += v * (v - 1) // 2


if (allCount == 0):
    for i in range(N):
        print(0)
    exit()

for i in range(N):
    a = allCount
    num = c[A[i]] - 1
    if (num == 1 or num == 0):
        print(allCount - num)
        continue
    old = c[A[i]] * (c[A[i]] - 1) // 2
    count = num * (num - 1) // 2
    print(a - old + count)
### BUGGY CODE ###

import random


n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 13

n = 15
info = []
for i in range(n):
    info.append([random.randint(-10000, 10000), random.randint(-10000, 10000), random.randint(1, 1000000)])


costs = [INF] * n
for i, (x, y, c) in enumerate(info):
    costs[i] = c * min(abs(x), abs(y))


x_dir = [INF] * ((1 << n) * n)
y_dir = [INF] * ((1 << n) * n)
OFFSET = (1 << n)


for bit_state in range(1 << n):
    for i, (xi, yi, c) in enumerate(info):
        x_dir[bit_state + i * OFFSET] = min(costs[i], x_dir[bit_state + i * OFFSET])
        y_dir[bit_state + i * OFFSET] = min(costs[i], y_dir[bit_state + i * OFFSET])
        if not((bit_state >> i) & 1):
            continue
        for j, (xj, yj, c) in enumerate(info):
            x_dir[bit_state + j * OFFSET] = min(x_dir[bit_state + j * OFFSET], c * abs(yi - yj))
            y_dir[bit_state + j * OFFSET] = min(y_dir[bit_state + j * OFFSET], c * abs(xi - xj))


ans = [INF] * (n + 1)
for bit_state in range((1 << n) - 1):
    x_bit = bit_state
    cnt = bin(bit_state).count("1")
    while x_bit >= 0:
        x_bit &= bit_state
        # bit_stateの下位集合sub_stateの列挙
        # 処理はじめ
        y_bit = bit_state - x_bit
        tmp = 0
        for i in range(n):
            tmp += min(x_dir[x_bit + i * OFFSET], y_dir[y_bit + i * OFFSET])
        ans[cnt] = min(ans[cnt], tmp)
        # 処理おわり
        x_bit -= 1

ans[-1] = 0
for res in ans:
    print(res)

### FIXED CODE ###

#import random


n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 13

#n = 15
#info = []
#for i in range(n):
#    info.append([random.randint(-10000, 10000), random.randint(-10000, 10000), random.randint(1, 1000000)])


costs = [INF] * n
for i, (x, y, c) in enumerate(info):
    costs[i] = c * min(abs(x), abs(y))

OFFSET = n
x_dir = [INF] * ((1 << n) * OFFSET)
y_dir = [INF] * ((1 << n) * OFFSET)


for bit_state in range(1 << n):
    for i, (xi, yi, c) in enumerate(info):
        x_dir[bit_state * OFFSET + i] = min(costs[i], x_dir[bit_state * OFFSET + i])
        y_dir[bit_state * OFFSET + i] = min(costs[i], y_dir[bit_state * OFFSET + i])
        if not((bit_state >> i) & 1):
            continue
        for j, (xj, yj, c) in enumerate(info):
            x_dir[bit_state * OFFSET + j] = min(x_dir[bit_state * OFFSET + j], c * abs(yi - yj))
            y_dir[bit_state * OFFSET + j] = min(y_dir[bit_state * OFFSET + j], c * abs(xi - xj))


ans = [INF] * (n + 1)
for bit_state in range((1 << n) - 1):
    x_bit = bit_state
    cnt = bin(bit_state).count("1")
    while x_bit >= 0:
        x_bit &= bit_state
        # bit_stateの下位集合sub_stateの列挙
        # 処理はじめ
        y_bit = bit_state - x_bit
        tmp = 0
        for i in range(n):
            tmp += min(x_dir[x_bit * OFFSET + i], y_dir[y_bit * OFFSET + i])
        ans[cnt] = min(ans[cnt], tmp)
        # 処理おわり
        x_bit -= 1

ans[-1] = 0
for res in ans:
    print(res)
### BUGGY CODE ###

n = int(input())
s = list(input())
l = []
for i in range(n):
    l.append(s[i+1:].count("E")+s[:i].count("W"))
print(min(l))

### FIXED CODE ###

n = int(input())
s = input()
cnt = s.count('E',1,n)
ans = [cnt]

for i in range(1,n):
    if s[i-1] == 'W': cnt += 1
    if s[i] == 'E': cnt -= 1
    ans.append(cnt)
print(min(ans))
### BUGGY CODE ###

from copy import *
from sys import *
from math import *
import queue
from collections import defaultdict,Counter,deque

setrecursionlimit(1000000)

#dp[i][w]
def main():
	n,w = map(int,input().split())
	wv = [list(map(int,input().split())) for i in range(n)]
	dp = [[0 for _ in range(w+1)] for _ in range(n+1)]
	for i in range(1,n+1):
		cw = wv[i-1][0]
		cv = wv[i-1][1]
		for j in range(w+1):
			dp[i][j] = max(dp[i-1][j],dp[i-1][j-cw] + cv) if j-cw >= 0 else dp[i-1][j]
	print(dp[-1][-1])

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(m,n):
	x = max(m,n)
	y = min(m,n)
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	return y

class Queue():
	#競プロ用のQueue
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)

class Stack():
	#怯プロ用のStack
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)

main()

### FIXED CODE ###

from copy import *
from sys import *
from math import *
import queue
from collections import defaultdict,Counter,deque

setrecursionlimit(1000000)

#dp[i][w]
def main():
	n,w = map(int,input().split())
	wv = [list(map(int,input().split())) for i in range(n)]
	dp = [[0 for _ in range(w+1)] for _ in range(n+1)]
	for i in range(1,n+1):
		cw = wv[i-1][0]
		cv = wv[i-1][1]
		for j in range(w+1):
			dp[i][j] = max(dp[i-1][j],dp[i-1][j-cw] + cv) if j-cw >= 0 else dp[i-1][j]
	print(dp[-1][-1])

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(m,n):
	x = max(m,n)
	y = min(m,n)
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	return y

class Queue():
	#競プロ用のQueue
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)

class Stack():
	#怯プロ用のStack
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)

main()
### BUGGY CODE ###

# R*r + G*g + B*b == N の数
R, G, B, N = map(int, input().split())
# R, G, B = list(sorted([R, G, B]))
ans = 0
for r in range(N+1):
    for g in range(N + 1):
        if (N - (r * R + g * G)) % B != 0:
            continue
        b = (N - (r * R + g * G))/B
        if b < 0:
            break
        if r * R + g * G + b * B == N:
            ans += 1
print(ans)


### FIXED CODE ###

# R*r + G*g + B*b == N の数
R, G, B, N = map(int, input().split())
R, G, B = list(sorted([R, G, B], reverse=True))
ans = 0
for r in range(N + 1):
    for g in range(N + 1):
        if (N - (r * R + g * G)) % B != 0:
            continue
        b = (N - (r * R + g * G))/B
        if b < 0:
            break
        if r * R + g * G + b * B == N:
            ans += 1
        elif r * R + g * G + b * B > N:
            break

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

[R, C, K] = list(map(int, input().split()))
G = [[None]*C for i in range(R)]
for i in range(K):
    [r, c, v] = list(map(int, input().split()))
    G[r-1][c-1] = v

dp = [[[0]*4 for i in range(C)] for j in range(R)]
path = [[[False]*4 for i in range(C)] for j in range(R)]
dp[0][0][0] = 0
path[0][0][0] = True
if G[0][0] != None:
    dp[0][0][1] = G[0][0]
    path[0][0][1] = True

for r in range(R):
    for c in range(C):
        for k in range(4):
            if path[r][c][k] == False: continue

            if c+1<C and G[r][c+1] != None and k < 3: # can go right and pick up
                dp[r][c+1][k+1] = max(dp[r][c+1][k+1], dp[r][c][k] + G[r][c+1])
                path[r][c+1][k+1] = True
            if c+1<C: # moving right without picking up
                dp[r][c+1][k] = max(dp[r][c+1][k], dp[r][c][k])
                path[r][c+1][k] = True
            if r+1<R: # moving downward without picking up
                dp[r+1][c][0] = max(dp[r+1][c][0], dp[r][c][k])
                path[r+1][c][0] = True
            if r+1<R and G[r+1][c] != None: # can go right and pick up
                dp[r+1][c][1] = max(dp[r+1][c][1], dp[r][c][k] + G[r+1][c])
                path[r+1][c][1] = True

print(max(dp[r][c]))
            


### FIXED CODE ###

import numpy as np
from numba import jit

R, C, K = map(int, input().split())
G = np.zeros((R+1, C+1), np.int64)
for i in range(K):
    [r, c, v] = list(map(int, input().split()))
    G[r-1][c-1] = v

@jit
def main(G, R, C):
    dp = np.full((R+1, C+1, 4), -1)
    dp[0][0][0] = 0
    if G[0][0] != None: dp[0][0][1] = G[0][0]
    for r in range(R):
        for c in range(C):
            for k in range(4):
                if dp[r][c][k] == -1: continue
                if k < 3: # can go right and pick up
                    if dp[r][c+1][k+1] < dp[r][c][k] + G[r][c+1]:
                        dp[r][c+1][k+1] = dp[r][c][k] + G[r][c+1]
                if dp[r][c+1][k] < dp[r][c][k]:
                    dp[r][c+1][k] = dp[r][c][k]
                if dp[r+1][c][0] < dp[r][c][k]:
                    dp[r+1][c][0] = dp[r][c][k]
                if dp[r+1][c][1] < dp[r][c][k] + G[r+1][c]:
                    dp[r+1][c][1] = dp[r][c][k] + G[r+1][c]
    return(max(dp[r][c]))

ret = main(G, R, C)
print(ret)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
B = []

for a in A:
    B.append(str(a))
    B = B[::-1]

print(" ".join(B))


### FIXED CODE ###

from collections import deque

n = int(input())
A = list(map(int, input().split()))
B = deque([])

if n % 2 == 0:
    for i in range(n):
        if i % 2 == 0:
            B.append(A[i])
        else:
            B.appendleft(A[i])

else:
    for i in range(n):
        if i % 2 == 0:
            B.appendleft(A[i])
        else:
            B.append(A[i])

B = list(map(str, B))
print(" ".join(B))
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]
ans = 1
for i in A:
    ans *= i
if ans <= 10**18:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]
if min(A) == 0:
    print(0)
else:
    ans = 1
    M = 10**18
    for i in A:
        ans *= i
        if ans > M:
            print(-1)
            break
    else:
        print(ans)
### BUGGY CODE ###

n = int(input())
l = sorted(list(map(int,input().split())))
ans = 0
import bisect
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            if abs(l[i]-l[j])<l[k]<l[i]+l[j]:
                ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
l = sorted(list(map(int,input().split())))
ans = 0
import bisect
for i in range(n):
    for j in range(i+1,n):
        a = l[i]+l[j]
        x = bisect.bisect_left(l,a)
        if x>j:
            ans += max(0,x-j-1)
print(ans)
### BUGGY CODE ###

n = int(input())
a = input()
inva = ''.join(map(lambda x: str(int(x) ^ 1), a))

mod = 998244353
ans = 0
p = 1
num = [0] * -~n
for i in range(n):
    if i:
        num[i] += (num[i - 1] * 2) % mod
    if a[i] == '1':
        num[i] += 1


def get_div(x):
    y = []
    for i in range(1, n):
        if x % i == 0 and (x // i) % 2:
            y.append(i)
    return y


div = get_div(n)
d = [0] * -~n
tot = 0
for i in div:
    now = n // i
    tt = num[i - 1]
    for j in get_div(i):
        tt -= d[j]
    k = (a[:i] + inva[:i]) * (n // (2 * i)) + a[:i]
    d[i] = tt + (int(a, 2) >= int(k, 2))
    tot += d[i]
d[n] = int(a, 2) + 1 - tot

for i in range(n + 1):
    ans = (ans + d[i] * i * 2) % mod

print(ans % mod)


### FIXED CODE ###

n = int(input())
a = input()
inva = ''.join(map(lambda x: str(int(x) ^ 1), a))

mod = 998244353
ans = 0
p = 1
num = [0] * -~n
for i in range(n):
    if i:
        num[i] += (num[i - 1] * 2) % mod
    if a[i] == '1':
        num[i] += 1


def get_div(x):
    y = []
    for i in range(1, n):
        if x % i == 0 and (x // i) % 2:
            y.append(i)
    return y


div = get_div(n)
d = [0] * -~n
tot = 0
for i in div:
    now = n // i
    tt = num[i - 1]
    for j in get_div(i):
        tt -= d[j]
    k = (a[:i] + inva[:i]) * (n // (2 * i)) + a[:i]
    d[i] = tt + (a >= k)
    tot += d[i]
d[n] = int(a, 2) + 1 - tot

for i in range(n + 1):
    ans = (ans + d[i] * i * 2) % mod

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

import sys
input = sys.stdin.readline
from collections import deque
h,w,k = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
grid = [input().rstrip() for i in range(h)]
dp = [[10**6 for i in range(w)] for j in range(h)]
dp[sx-1][sy-1] = 0
q = deque()
q.append((sx-1,sy-1,0,1))
while q:
  px,py,direc,dis = q.popleft()
  for j in range(1 if direc != "U" else dis,k+1):
    if px+j >= h or grid[px+j][py] == "@" or dp[px+j][py] <= dp[px][py]:
      break
    dp[px+j][py] = dp[px][py]+1
    q.append((px+j,py,"U",k-j+1))
  for j in range(1 if direc != "D" else dis,k+1):
    if px-j < 0 or grid[px-j][py] == "@" or dp[px-j][py] <= dp[px][py]:
      break
    dp[px-j][py] = dp[px][py]+1
    q.append((px-j,py,"D",k-j+1))
  for j in range(1 if direc != "L" else dis,k+1):
    if py+j >= w or grid[px][py+j] == "@" or dp[px][py+j] <= dp[px][py]:
      break 
    dp[px][py+j] = dp[px][py]+1
    q.append((px,py+j,"L",k-j+1))
  for j in range(1 if direc != "R" else dis,k+1):
    if py-j < 0 or grid[px][py-j] == "@" or dp[px][py-j] <= dp[px][py]:
      break
    dp[px][py-j] = dp[px][py]+1
    q.append((px,py-j,"R",k-j+1))
if dp[gx-1][gy-1] == 10**6:
  print(-1)
else:
  print(dp[gx-1][gy-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque
h,w,k = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
grid = [input().rstrip() for i in range(h)]
dp = [[10**6 for i in range(w)] for j in range(h)]
dp[sx-1][sy-1] = 0
q = deque()
q.append((sx-1,sy-1))
while q:
  px,py = q.popleft()
  d = dp[px][py]
  for j in range(1,k+1):
    if px+j >= h or grid[px+j][py] == "@" or dp[px+j][py] <= d:
      break
    if dp[px+j][py] == 10**6:
      dp[px+j][py] = d+1
      q.append((px+j,py))
  for j in range(1,k+1):
    if px-j < 0 or grid[px-j][py] == "@" or dp[px-j][py] <= d:
      break
    if dp[px-j][py] == 10**6:
      dp[px-j][py] = d+1
      q.append((px-j,py))
  for j in range(1,k+1):
    if py+j >= w or grid[px][py+j] == "@" or dp[px][py+j] <= d:
      break 
    if dp[px][py+j] == 10**6:
      dp[px][py+j] = d+1
      q.append((px,py+j))
  for j in range(1,k+1):
    if py-j < 0 or grid[px][py-j] == "@" or dp[px][py-j] <= d:
      break
    if dp[px][py-j] == 10**6:
      dp[px][py-j] = d+1
      q.append((px,py-j))
if dp[gx-1][gy-1] == 10**6:
  print(-1)
else:
  print(dp[gx-1][gy-1])
### BUGGY CODE ###

import networkx as nx
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


G = nx.Graph()
N, M = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(M)]
G.add_edges_from(edge)
path = nx.single_source_shortest_path(G, source=1)

print("Yes")
for i in range(2, N + 1):
    print(path[i][-2])

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
edge = [[] for _ in range(N + 1)]
for _ in range(M):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)

prev = [None] * (N + 1)
seen = [False] * (N + 1)
node = deque([1])
seen[1] = True

while node:
    s = node.popleft()
    for t in edge[s]:
        if not seen[t]:
            seen[t] = True
            prev[t] = s
            node.append(t)

if any(x is None for x in prev[2:]):
    print("No")
else:
    print("Yes")
    print(*prev[2:], sep="\n")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
al = list(map(int, input().split()))
al_cnt = [0] * (n + 1)

for i in range(1, n + 1):
    al_cnt[i] = al.count(i)
max_cnt = 0

for j in range(1, n + 1):
    if al_cnt[j] >= 2:
        max_cnt += al_cnt[j] * (al_cnt[j] - 1) / 2

for l in range(n):
    if al_cnt[al[l]] >= 3:
        ans = max_cnt - (al_cnt[al[l]] * (al_cnt[al[l]] - 1) / 2) + ((al_cnt[al[l]] - 1) * (al_cnt[al[l]] - 2) / 2)
        print(int(ans) if ans > 0 else 0)
    else:
        ans = max_cnt - (al_cnt[al[l]] * (al_cnt[al[l]] - 1) / 2)
        print(int(ans) if ans > 0 else 0)


### FIXED CODE ###

from collections import Counter

n = int(input())
al = list(map(int, input().split()))
al_cnt = Counter(al)
ans = sum([i * (i - 1) // 2 for i in al_cnt.values()])
for j in al:
    print(ans - al_cnt[j] + 1)
### BUGGY CODE ###

import collections
n = int(input())
s = input()
minn = n
for i in range(n):
    l = s[:i].count("W")
    r = s[i + 1:].count("E")
    if minn > l + r:
        minn = l + r
print(minn)


### FIXED CODE ###

import collections
n = int(input())
s = input()
l = s.count("W")
r = s.count("E")
ans = 0
keep = r
minn = keep
if s[0] == "E":
    ans = 1
for i in range(1, n):
    if s[i - 1:i + 1] == "WW":
        keep += 1
    elif s[i - 1:i + 1] == "WE":
        keep += 0
    elif s[i - 1:i + 1] == "EW":
        keep += 0
    elif s[i - 1:i + 1] == "EE":
        keep -= 1
    if minn > keep:
        minn = keep
print([minn, minn - 1][ans])