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

#from pprint import pprint
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。

# = map(int,input().split())

# = list(map(int,input().split()))

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

from collections import deque






n,m = map(int,input().split())

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

ab_count = {key:[] for key in range(1,n+1)}

for i in range(m):
    ab_count[ab_list[i][0]].append(ab_list[i][1])
    ab_count[ab_list[i][1]].append(ab_list[i][0])


#print(ab_count)

que = deque()

#始点は1、階層は0からスタート
que.append([1,0])

checked_dict = {key:[] for key in range(1,n+1)}
temp_dict = {key:[] for key in range(1,n+1)}
where = 0

while que:
    x_pop = que.popleft()
    x = x_pop[0]
    if where != x_pop[1]:
        #階層が代わったから、temp_dictをchecked_dictへ反映させる処理
        for k in range(1,n+1):
            if len(checked_dict[k]) == 0:
                checked_dict[k] = temp_dict[k]
            elif set(checked_dict[k]) & set(temp_dict[k]) != set():
                checked_dict[k] = list(set(checked_dict[k]) & set(temp_dict[k]))

    
    where = x_pop[1]

    for j in ab_count[x]:
        if len(checked_dict[j]) == 0:
            #OK,temp_dictに入れて、queに入れる。
            temp_dict[j].append(x)
            que.append([j,where+1])
        else:
            continue

    

print("Yes")
for i in range(2,n+1):
    print(checked_dict[i][0])

### FIXED CODE ###

from collections import deque


n,m = map(int,input().split())

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

ab_count = {key:[] for key in range(1,n+1)}

for i in range(m):
    ab_count[ab_list[i][0]].append(ab_list[i][1])
    ab_count[ab_list[i][1]].append(ab_list[i][0])


#print(ab_count)

que = deque()

#始点は1、階層は0からスタート
que.append([1,0])

checked_dict = {key:[] for key in range(1,n+1)}
#temp_dict = {key:[] for key in range(1,n+1)}
where = 0

while que:
    x_pop = que.popleft()
    x = x_pop[0]
    if where != x_pop[1]:
        pass
        ##階層が代わったから、temp_dictをchecked_dictへ反映させる処理
        #for k in range(1,n+1):
        #    if len(checked_dict[k]) == 0:
        #        checked_dict[k] = temp_dict[k]
        #    else:
        #        aaa = set(checked_dict[k]) & set(temp_dict[k])
        #        if aaa != set():
        #            checked_dict[k] = list(aaa)

    where = x_pop[1]

    for j in ab_count[x]:
        if len(checked_dict[j]) == 0:
            #OK,temp_dictに入れて、queに入れる。
            #temp_dict[j].append(x)
            checked_dict[j].append(x)
            que.append([j,where+1])
        else:
            continue

    

print("Yes")
for i in range(2,n+1):
    print(checked_dict[i][0])
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [10**9 for _ in range(N)]
    dp[0] = 0
    for i in range(N):
        for j in range(1, K+1):
            if i+j < N:
                dp[i+j] = min(dp[i+j], dp[i]+abs(h[i+j]-h[i]))
    print(dp[-1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [10**9 for _ in range(N)]
    dp[0] = 0
    for i in range(N):
        for j in range(1, K+1):
            if i+j < N:
                dp[i+j] = min(dp[i+j], dp[i]+abs(h[i+j]-h[i]))
    print(dp[-1])


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

s_origin = str(input())

s = s_origin.replace("00000000001111111111", "")
s = s.replace("11111111110000000000", "")
s = s.replace("000000000111111111", "")
s = s.replace("111111111000000000", "")
s = s.replace("0000000011111111", "")
s = s.replace("1111111100000000", "")
s = s.replace("00000001111111", "")
s = s.replace("11111110000000", "")
s = s.replace("000000111111", "")
s = s.replace("111111000000", "")
s = s.replace("0000011111", "")
s = s.replace("1111100000", "")
s = s.replace("00001111", "")
s = s.replace("11110000", "")
s = s.replace("000111", "")
s = s.replace("111000", "")
s = s.replace("0011", "")
s = s.replace("1100", "")
s = s.replace("01", "")
s_aft = s.replace("10", "")

s_bef = s_origin
while len(s_bef) > len(s_aft):
    s_bef, s_aft = s_aft, s_aft.replace("01", "").replace("10", "")

print (len(s_origin) - len(s_aft))

### FIXED CODE ###

s = str(input())
q = s[0]
for c in s[1:]:
    if len(q) >= 1:
        if q[-1] != c:
            q = q[:-1]
        else:
            q += c
    else:
        q += c
print(len(s) - len(q))
### BUGGY CODE ###

N,Q = [int(x) for x in input().split()]
S = input()
l = [0]*Q
r = [0]*Q
for i in range(Q):
    l[i],r[i] = [int(x) for x in input().split()]

for i in range(Q):
    s = S[l[i]-1:r[i]]
    state = 0
    ans = 0
    for j in s:
        if(state == 0):
            if(j == 'A'):
                state = 1
        elif(state == 1):
            if(j == 'C'):
                ans +=1
            state = 0
    print(ans)


### FIXED CODE ###

N,Q = [int(x) for x in input().split()]
S = input()
l = [0]*Q
r = [0]*Q
li = [0]*(N+1)
for i in range(Q):
    l[i],r[i] = [int(x) for x in input().split()]
state = 0
for index,j in enumerate(S):
    li[index+1]=li[index]
    if(state == 1):
        if(j == 'C'):
            li[index+1]+=1
        state = 0
    if(j == 'A'):
        state = 1
        
for i in range(Q):
    print(li[r[i]]-li[l[i]])
### BUGGY CODE ###

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

b = []
for i in range(n) :
    ai = alist[i]
    b.append(ai)
    b.reverse()

for bi in b :
    print(bi, end=" ")

### FIXED CODE ###

from collections import deque
n = int(input())
alist = deque(map(int, input().split()))

blist = deque([])
for i in range(n) :
    bi = alist.popleft()
    if (n^i)&1 == 1 :
        blist.appendleft(bi)
    else :
        blist.append(bi)

for b in blist :
    print(b, end=" ")
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b = 1
for i in range(n):
    b = b * a[i]
count = 0
while (b % 2 == 0):
    count += 1
    b = b // 2
print(count)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
count = 0
for i in a:
    while (i % 2 == 0):
        count += 1
        i = i // 2
print(count)
### BUGGY CODE ###

import sys
finput=lambda:sys.stdin.readline().strip()

def main():
    p=10**9+7
    n=int(finput())
    a=list(map(int,finput().split()))
    k=sum(a)-(n*(n+1))//2
    pk=[i for i in range(n+1) if a[i]==k]
    fact=[1]*(n+2)
    ifact=[1]*(n+2)
    for i in range(1,n+2):
        fact[i]=fact[i-1]*i % p
    a=fact[-1]
    inv=1
    m=p-2
    while m>0:
        if m&1:
            inv=a*inv % p
        m>>=1
        a=a*a % p
    ifact[-1]=inv
    for i in range(n+1,0,-1):
        ifact[i-1]=ifact[i]*i
    ans0=[0]*(n+2)
    ans1=[0]*(n+2)
    ans2=[0]*(n+2)
    for i in range(n):
        ans0[i]=fact[n-1]*ifact[n-i-1]*ifact[i]%p
        ans1[i+1]=ans0[i]*2
        ans2[i+2]=ans0[i]
    sn=pk[0]+n-pk[1]
    for i in range(sn+1):
        ans1[i+1]-=fact[sn]*ifact[sn-i]*ifact[i] % p
    for i in range(1,n+2):
        print((ans0[i]+ans1[i]+ans2[i]) % p)

if __name__=='__main__':
    main()


### FIXED CODE ###

import sys
finput=lambda:sys.stdin.readline().strip()

def main():
    p=10**9+7
    n=int(finput())
    a=list(map(int,finput().split()))
    k=sum(a)-(n*(n+1))//2
    pk=[i for i in range(n+1) if a[i]==k]
    fact=[1]*(n+2)
    ifact=[1]*(n+2)
    for i in range(1,n+2):
        fact[i]=fact[i-1]*i % p
    a=fact[-1]
    inv=1
    m=p-2
    while m>0:
        if m&1:
            inv=a*inv % p
        m>>=1
        a=a*a % p
    ifact[-1]=inv
    for i in range(n+1,0,-1):
        ifact[i-1]=ifact[i]*i % p
    ans0=[0]*(n+2)
    ans1=[0]*(n+2)
    ans2=[0]*(n+2)
    for i in range(n):
        ans0[i]=fact[n-1]*ifact[n-i-1]*ifact[i]%p
        ans1[i+1]=ans0[i]*2
        ans2[i+2]=ans0[i]
    sn=pk[0]+n-pk[1]
    for i in range(sn+1):
        ans1[i+1]-=fact[sn]*ifact[sn-i]*ifact[i] % p
    for i in range(1,n+2):
        print((ans0[i]+ans1[i]+ans2[i]) % p)

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

S = input()
Q = int(input())
cond = 1
for i in range(Q):
	q = list(map(str, input().split()))
	if q[0] == "1":
		cond *= -1
	else:
		if q[1] == "1":
			if cond == 1:
				S = q[2] + S
			else:
				S += q[2]
		else:
			if cond == 1:
				S += q[2]
			else:
				S = q[2] + S

if cond == 1:
	print(S)
else:
	print(S[::-1])

### FIXED CODE ###

S = input()
Q = int(input())
cond = 1
pre = ''
epi = ''
for i in range(Q):
	q = list(map(str, input().split()))
	if q[0] == "1":
		cond *= -1
	else:
		if q[1] == "1":
			if cond == 1:
				pre += q[2]
			else:
				epi += q[2]
		else:
			if cond == 1:
				epi += q[2]
			else:
				pre += q[2]

if cond == 1:
	print(pre[::-1]+S+epi)
else:
	print(epi[::-1]+S[::-1]+pre)
### BUGGY CODE ###

lst = [int(i) for i in input().split()]

ball = lst[0]
blue = lst[1]
red = lst[2]
blue_red = int(ball / (red + blue)) + 1

blue_str = ''
for i in range(blue): blue_str += 'b'
red_str = ''
for i in range(red): red_str += 'r'

mojiretu = ''
for i in range(blue_red): mojiretu += (blue_str + red_str)
print(mojiretu[:ball].count('b'))

### FIXED CODE ###

lst = [int(i) for i in input().split()]
ball = lst[0]
blue = lst[1]
red = lst[2]

red_blue = int(ball / (red + blue))
shokichi = red_blue * blue
amari = ball - (red_blue * (red + blue))

if amari < blue:
    nokori = amari
elif amari > blue:
    nokori = blue
else:
    nokori = 0

if blue == 0:
    print(0)
else:
    print(shokichi + nokori)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main(n, s_array):
    count = 0
    for i in range(n):
        for j in range(i+1, n):
            if(s_array[i] == s_array[j]):
                count += 1
    return count


if __name__ == "__main__":
    n = int(input())
    s_array = [sorted(input()[:-1]) for _ in range(n)]

    print(main(n, s_array))


### FIXED CODE ###

import sys
input = sys.stdin.readline


if __name__ == "__main__":
    n = int(input())
    s_array = [''.join(sorted(input()[:-1])) for _ in range(n)]

    s_array.sort()
    ans = 0
    count = 0
    word = s_array[0]
    for i in range(1, n):
        if(word == s_array[i]):
            count += 1
        else:
            ans += (count*(count+1))//2
            count = 0
        word = s_array[i]

    ans += (count*(count+1))//2
    print(ans)
### BUGGY CODE ###

N = int(input())
mylist = map(int,input().split())
myans = 1
for m in mylist:
    myans *= m
if myans <= 10**18:
    print(myans)
else:
    print(-1)


### FIXED CODE ###

import math
import sys
N = int(input())
mylist = list(map(int, input().split()))
mylist.sort(reverse = True)
#print(mylist)
if mylist[-1] == 0:
    print(0)
    sys.exit()
else:
    myans = 1
    for m in mylist:
        myans *= m
        if myans > 10**18:
            print(-1)
            sys.exit()
    print(myans)
### BUGGY CODE ###

import sys
from itertools import product

input = sys.stdin.readline

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]

for i, j in product(range(H), range(W)):
    if S[i][j] == '#':
        continue
    if j == 0:
        L[i][j] = 1
    else:
        L[i][j] = L[i][j - 1] + 1
    if i == 0:
        U[i][j] = 1
    else:
        U[i][j] = U[i - 1][j] + 1

for i, j in product(range(H), range(W - 1, -1, -1)):
    if S[i][j] == '#':
        continue
    if j == W - 1:
        R[i][j] = 1
    else:
        R[i][j] = R[i][j + 1] + 1

for i, j in product(range(H - 1, -1, -1), range(W)):
    if S[i][j] == '#':
        continue
    if i == H - 1:
        D[i][j] = 1
    else:
        D[i][j] = D[i + 1][j] + 1

ans = 0
for i, j in product(range(H), range(W)):
    if S[i][j] == '#':
        continue
    x = L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3
    ans = max(ans, x)
print(ans)


### FIXED CODE ###

import sys
from itertools import product

input = sys.stdin.readline

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]

for i, j in product(range(H), range(W)):
    if S[i][j] == '#':
        continue
    if j == 0:
        L[i][j] = 1
    else:
        L[i][j] = L[i][j - 1] + 1
    if i == 0:
        U[i][j] = 1
    else:
        U[i][j] = U[i - 1][j] + 1

for i, j in product(range(H), range(W - 1, -1, -1)):
    if S[i][j] == '#':
        continue
    if j == W - 1:
        R[i][j] = 1
    else:
        R[i][j] = R[i][j + 1] + 1

for i, j in product(range(H - 1, -1, -1), range(W)):
    if S[i][j] == '#':
        continue
    if i == H - 1:
        D[i][j] = 1
    else:
        D[i][j] = D[i + 1][j] + 1

ans = 0
for i, j in product(range(H), range(W)):
    if S[i][j] == '#':
        continue
    x = L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3
    ans = max(ans, x)
print(ans)
### BUGGY CODE ###

n=int(input())
li=list(map(int, input().split()))
ans=1
for i in range(1,n):
    lis=li[:i]
    if min(lis)>=li[i]:
        ans=ans+1
print(ans)


### FIXED CODE ###

n=int(input())
li=list(map(int, input().split()))
ans=0
min=li[0]
for i in range(n):
    if li[i]<=min:
        ans=ans+1
        min=li[i]

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

n = int(input())
a = list(int(i) for i in input().split())
sa = [0] * (n+1)
num_cnt = {}    
# 累積和
for i in range(n):
    sa[i+1] = sa[i] + a[i]

nums = list(set(sa))
for num in nums:
    num_cnt[num] = sa.count(num)
res = 0
for cnt in num_cnt.values():
    res += cnt*(cnt-1)//2

print(res)

### FIXED CODE ###


n = int(input())
a = list(int(i) for i in input().split())
sa = [0] * (n+1)
num_cnt = {}    
# 累積和
for i in range(n):
    sa[i + 1] = sa[i] + a[i]

for num in sa:
    if num in num_cnt:
        num_cnt[num] += 1
    else:
        num_cnt[num] = 1


res = 0
for cnt in num_cnt.values():
    res += cnt*(cnt-1)//2

print(res)
### 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 ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, Q = MAP()
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b = MAP()
    nodes[a-1].append(b-1)

ans = [0] * N
for i in range(Q):
    p, x = MAP()
    ans[p-1] += x

def dfs(u, prev, cnt):
    ans[u] += cnt
    for v in nodes[u]:
        dfs(v, u, ans[u])
dfs(0, -1, 0)

print(*ans)


### FIXED 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 ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, Q = MAP()
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b = MAP()
    nodes[a-1].append(b-1)

ans = [0] * N
for i in range(Q):
    p, x = MAP()
    ans[p-1] += x

def dfs(u, prev, cnt):
    ans[u] += cnt
    for v in nodes[u]:
        if v != prev:
            dfs(v, u, ans[u])
dfs(0, -1, 0)

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

import itertools
import collections

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

comb = list(itertools.combinations(list(s), 3))

print(len(collections.Counter(comb)))


### FIXED CODE ###

import itertools
import collections

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

password_l = [str(i).zfill(3) for i in range(1000)]

c = 0
for password in password_l:
    idx = 0
    ok = 0
    while idx != n:
        if s[idx] == password[ok]:
            ok += 1
        
        if ok == 3:
            c += 1
            break
        
        idx += 1

print(c)
### BUGGY CODE ###

N = int(input())
S = input()
ans = float("inf")
for i in range(N):
	ans = min(ans, S[i + 1:].count("E") + S[: i].count("W"))
print(ans)


### FIXED CODE ###

N = int(input())
S = input()
ans = [S[1:].count("E")]
for i in range(1, N):
	tmp = ans[i - 1]
	if S[i - 1] == "W":
		tmp += 1
	if S[i] == "E":
		tmp -= 1
	ans.append(tmp)
print(min(ans))
### BUGGY CODE ###

import copy


n = int(input())
lst = list(map(int,input().split(' ')))

for i in range(n):
    l = copy.deepcopy(lst)
    del l[i]
    buf = 0
    for ll in l:
        buf ^= ll
    print(buf)

### FIXED CODE ###

n = int(input())
lst = list(map(int,input().split(' ')))

x = 0
for l in lst:
    x ^= l
out = ''
for l in lst:
    out += ' ' + str(x^l)
print(out[1:])
### BUGGY CODE ###

from itertools import accumulate
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

dp = [[float('inf')]*N for _ in range(N)]
a_acc = [0]+list(accumulate(A))
for i in range(N):
    dp[i][i] = 0


def dfs(l, r):
    """
    List[l:r]
    """
    #print("l,r->", l, r)
    # print(A[l:r])
    if dp[l][r-1] != float('inf'):
        return dp[l][r-1]
    if r-l == 1:
        # print("sole")
        return 0
    if r-l == 2:
        # print("double")
        dp[l][r-1] = A[l]+A[r-1]
        return dp[l][r-1]
    elif r-l <= 0:
        # print("err")
        return 0
    else:
        if l+2 >= r:
            #print("err->ret empty")
            return -1
        else:
            # print("update")
            dp[l][r-1] = min(dfs(l, v)+dfs(v, r)
                             for v in range(l+1, r))+a_acc[r]-a_acc[l]
            return dp[l][r-1]


dfs(0, N)
#print("ans->", dp[0][-1])
print(dp[0][-1])


### FIXED CODE ###

from itertools import accumulate
import sys
# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

dp = [[float(0)]*N for _ in range(N)]
a_acc = [0]+list(accumulate(A))


def dfs(l, r):
    """
    List[l:r]
    """
    if dp[l][r-1] != float('inf'):
        return dp[l][r-1]
    if r-l == 1:
        dp[l][r-1] = 0
        return 0
    if r-l == 2:
        dp[l][r-1] = A[l]+A[r-1]
        return dp[l][r-1]
    else:
        dp[l][r-1] = min(dfs(l, v)+dfs(v, r)
                         for v in range(l+1, r))+a_acc[r]-a_acc[l]
        return dp[l][r-1]


def bfs():
    for d in range(2, N+1):
        for l in range(0, N-d+1):
            r = l + d
            #print("l,r->", l, r)
            tmp = float('inf')
            for m in range(l+1, r):
                tmp = min(tmp, dp[l][m-1]+dp[m][r-1])
            #print("tmp->", tmp)
            #print("acc->", a_acc[r]-a_acc[l])
            dp[l][r-1] = tmp+a_acc[r]-a_acc[l]


# print(a_acc)
bfs()
# print(dp)
ans = int(dp[0][-1])
print(ans)
### BUGGY CODE ###

import bisect

n, m = map(int, input().split())
a = list(map(int, input().split()))
l = []

for _ in range(m):
    l.append(list(map(int, input().split())))

a.sort()
l.sort(key=lambda x: x[1], reverse=True)

focus = 0
for b, c in l:
    for j in range(focus, focus+b):
        if j < n: a[j] = max(c, a[j])
    focus += b

print(sum(a))


### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
l = []

for _ in range(m):
    l.append(list(map(int, input().split())))

a.sort()
l.sort(key=lambda x: x[1], reverse=True)

focus = 0
for b, c in l:
    for j in range(focus, min(focus+b, n)):
        a[j] = max(c, a[j])
    focus += b

print(sum(a))
### BUGGY CODE ###

number = list(map(int,input().split()))
line = list(map(int,input().split()))
 
num = number[0]
K = number[1]
dp = [float("inf")]* num
dp[0] = 0

for i in range(1, num):
  I = min(i + 1 , K + 1)
  dp[i] = min([dp[i - k] + abs(line[i] - line[i - k]) for k in range(1 , I)])
  #kの範囲: k = 1,2,3...K 無理なときは k = 1,2..i
  
print(dp[-1])

### FIXED CODE ###

def ans():
    n, k, *h = map(int, open(0).read().split())
    dp = [float("inf")] * n
    dp[0] = 0
    for i in range(1, n):
        min_j = max(0, i-k)
        dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(min_j , i)])
    print(dp[n-1])
 
ans()
### BUGGY CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))

INF = 10**9 + 1
L = [INF]*N
L[0] = 0
for i in range(1, N):
    for k in range(1, K+1):
        if i - k >= 0:
            L[i] = min(L[i], L[i-k] + abs(H[i] - H[i-k]))
print(L[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))

INF = 10**9 + 1
L = [INF]*N
L[0] = 0
for i in range(1, N):
    minLi = L[i]
    H_i = H[i]
    for k in range(1, K+1):
        if i - k >= 0:
            minLi = min(minLi, L[i-k] + abs(H_i - H[i-k]))
    L[i] = minLi
print(L[N-1])
### BUGGY CODE ###

import copy

def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    B = [0 for i in range(n)]
    for m in range(k):
        B = [1 for i in range(n)]
        for i in range(n):
            for j in range(A[i]):
                if 0 <= i - j - 1:
                    B[i - j - 1] += 1
                if i + j + 1 < n:
                    B[i + j + 1] += 1
        A = copy.deepcopy(B)

    for a in A:
        print(a, end=" ")

resolve()

### FIXED CODE ###

from numba import jit
import numpy as np

@jit
def resolve():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype=np.int64)
    for m in range(k):
        B = np.zeros(n + 1, dtype=np.int64)
        for i in range(n):
            l = max(0, i - A[i])
            r = min(n, i + A[i] + 1)
            B[l] += 1
            if r < n:
                B[r] -= 1
        A = np.cumsum(B)[:-1]
        if np.all(A == n):
            break

    for a in A:
        print(a, end=" ")

resolve()
### BUGGY CODE ###

n, k, q = map(int, input().split())
a = []

for i in range(q):
  a.append(int(input()))

points = [k for i in range(n)]

for i in range(len(a)):
  for j in range(n):
    if j != a[i]-1:
      points[j] -= 1

for i in range(n):
  if points[i] > 0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

n, k, q = map(int, input().split())
a = []

for i in range(q):
  a.append(int(input()))

points = [k for i in range(n)]
minus_ones = [-1 for i in range(n)]

for i in range(q):
    points[a[i]-1] += 1
  
for i in range(n):
    points[i] -= q

for i in range(n):
  if points[i] > 0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def solve():
    N = int(input())
    S = [input().rstrip() for i in range(N)]

    from collections import defaultdict
    T = defaultdict(lambda: set())
    for s in S:
        T[len(s)].add(s)

    ans = 0
    for s in S:
        pre = set([s[0]])
        for l in range(len(s)-1, 0, -1):
            pre.add(s[-l])
            if T[l]:
                for p in pre:
                    suf = '' if l==1 else s[-l+1:]
                    if p+suf in T[l]:
                        ans += 1
    print(ans)
solve()

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S = [input().rstrip()[::-1] for i in range(N)]
S.sort(key=len)
P = 2**61 - 1

from collections import defaultdict
D = defaultdict(lambda: [0]*26)

ans = 0
for s in S:
    l = ord(s[-1]) - ord('a')
    a = 0
    tmp = [0] * 26
    for c in s[:-1]:
        i = ord(c) - ord('a')
        if a in D:
            for j in range(26):
                tmp[j] += D[a][j]
        ans += tmp[i]
        tmp[i] = 0
        a = (a*27 + i + 1) % P
    ans += tmp[l]
    D[a][l] += 1

print(ans)