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

import numpy as np
from collections import Counter as C

n=int(input())
a = list(input().split())
a = [int(i) for i in a]
q=int(input())
bc=[list(map(int,input().split())) for i in range(q)]
bc=np.array(bc).T
b=bc[0]
c=bc[1]

d=C(a)
d2={}
for k,v in d.items():
  d2[k]=k*v

#print(d)
ans=sum(d2.values())
for i in range(q):
  #print(d2)
  if d.get(b[i]):
    #removed=d.pop(b[i])
    _=d2.pop(b[i])
    d[c[i]]+=d[b[i]]
    d2[c[i]]=c[i]*d[c[i]]
    d[b[i]]=0
  else:
    pass
  #print((np.array(list(d2.values()))))
  #ans+=(c[i]-b[i])*d[removed]
  print(sum(d2.values()))


### FIXED CODE ###

import numpy as np
from collections import Counter as C

n=int(input())
a = list(input().split())
a = [int(i) for i in a]
q=int(input())
bc=[list(map(int,input().split())) for i in range(q)]
bc=np.array(bc).T
b=bc[0]
c=bc[1]

d=C(a)
d2={}
for k,v in d.items():
  d2[k]=k*v

#print(d)
ans=sum(a)
for i in range(q):
  d[c[i]]+=d[b[i]]
  ans+=(c[i]-b[i])*d[b[i]]
  d[b[i]]=0
  print(ans)
### BUGGY CODE ###

N,K = map(int, input().split())
P = list(map(int,input().split()))
Px  =[0]*N
Pxx = []
for i in range(N):
    Px[i] = (1+P[i])/2
for j in range(N-K+1):
    temp_num = sum(Px[j:j+K])
    Pxx.append(temp_num)
print(max(Pxx))

### FIXED CODE ###

N,K = map(int, input().split())
P = list(map(int,input().split()))
Px  =[]
for i in range(N):
    Px.append((1+P[i])/2)
temp_num = sum(Px[0:K])
temp_max = sum(Px[0:K])
#print(Px)
for j in range(N-K):
    #print(temp_num)
    temp_num = temp_num-Px[j]+Px[j+K]
    if temp_max <temp_num:
        temp_max=temp_num
print(temp_max)
### BUGGY CODE ###

n = int(input())
l = []
r = []
for _ in range(n):
  a, b = map(int, input().split())
  l.append(a)
  r.append(b)
before_sa = 0
for i in range(1, n+1):
  j = 0
  a, b = l[-i], r[-i]
  while True:
    if j == 0 and a % b == 0:
      sa = 0
    elif j == 0 and a % b != 0:
      sa = (a//b + 1) * b - a
    elif j > 0:
      sa = (a//b + j) * b - a
    if before_sa <= sa:
      before_sa = sa
      break
    j += 1
print(before_sa)


### FIXED CODE ###

n = int(input())
l = []
r = []
for _ in range(n):
  a, b = map(int, input().split())
  l.append(a)
  r.append(b)
before_sa = 0
for i in range(1, n+1):
  a, b = l[-i], r[-i]
  a += before_sa
  if a % b == 0:
    continue
  else:
    sa = (a//b + 1) * b - a
    before_sa += sa
print(before_sa)
### BUGGY CODE ###

n,m=map(int,input().split())
list_p=[]
for i in range(0,m):
    a,b=map(int,input().split())
    list_p.append([a,b])
list_p.reverse()
group=[]
count=[]
group.append(list_p[0])
count.append(0)
for i in range(1,m):
    number=0
    index=0
    ifa=0
    ifb=0
    for j in group:
        number=number+len(j)*(len(j)-1)//2
        if list_p[i][0] in j:
            ifa=1
            placea=index
        if list_p[i][1] in j:
            ifb=1
            placeb=index
        index=index+1
    count.append(number)
    if ifa==0 and ifb==0:
        group.append(list_p[i])
    elif ifa==1 and ifb==0:
        group[placea].append(list_p[i][1])
    elif ifa==0 and ifb==1:
        group[placeb].append(list_p[i][0])
    elif ifa==1 and ifb==1:
        if placea==placeb:
            pass
        else:
            group[placea].extend(group[placeb])
            group.pop(placeb)
x=n*(n-1)//2
count.reverse()
for i in count:
    print(x-i)


    


### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size=[1]*(n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y]=self.size[x]+self.size[y]
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.size[x]=self.size[x]+self.size[y]

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def Size(self,x):
        return self.size[self.find(x)]

n,m=map(int,input().split())
a_list=[]
b_list=[]
for i in range(m):
    a,b=map(int,input().split())
    a_list.append(a)
    b_list.append(b)
ans=[n*(n-1)//2]
U=UnionFind(n)
for i in range(m-1,0,-1):
    if U.same_check(a_list[i],b_list[i]):
        ans.append(ans[-1])
    else:
        ans.append(ans[-1]-U.Size(a_list[i])*U.Size(b_list[i]))
        U.union(a_list[i],b_list[i])
for i in range(m-1,-1,-1):
    print(ans[i])
### BUGGY CODE ###

#a,b,c, = map(int,input().split())

a = list(map(int,input().split()))
a.sort(reverse=True)

cnt = 0
while True:
	if a[0] == a[1] == a[2]:
		break
	elif a[0] == a[1] > a[2]:
		if (a[0] - a[2])%2 == 0:
			cnt += (a[0] - a[2])//2
			a[2] = a[0]
		else:
			cnt += (a[0]+1 - a[2])//2
			cnt += 1
			a[0] += 1
			a[1] += 1
			a[2] = a[0]
	elif a[0] > a[1] > a[2]:
		a[1] += 1
		a[2] += 1
		cnt += 1

print(cnt)


### FIXED CODE ###

#和を求める解法
a,b,c = map(int,input().split(" "))
sum = a+b+c
max = max(a,b,c)
if (sum - max)%2 == 0:
    print(int((max*3 - sum)/2))
else:
    print(int(((max+1)*3 - sum)/2))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
if n % 2 == 0:
    for i in range(int(n/2)):
        b.append(a[n-1-2*i])
    for i in range(int(n/2)):
        b.append(a[2*i])    
else:
    for i in range(int((n + 1)/ 2)):
        b.append(a[n-2*i-1])
    for i in range(1,int((n + 1)/ 2)):
        b.append(a[2*i - 1])
        
c = ''
for i in range(len(b)):
    c = c + ' ' + str(b[i])
print(c)

### FIXED CODE ###

n = int(input())
ll = list(map(int,input().split()))
mm = []
pp = n
i = 0
for i in range(n):
    try:
        mm.append(str(ll[-1-2*i]))
        ll[-1-2*i] = '-1'
    except:
        pass

    
for i in range(len(ll)):
    if ll[i] != '-1':
        mm.append(str(ll[i]))
    else:
        None
        
sss = ''
for i in mm:
    print(i, end= ' ')
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
sort = sorted(A)
amari = []
while len(amari) != 1:
  amari.clear()
  if 0 in sort: sort.remove(0)
  for item in sort:
    if item%sort[0] not in amari:
      amari.append(item%sort[0])
  last_sort0 = sort[0]
  sort = sorted(amari[:])
  sort.append(last_sort0)

print(last_sort0-amari[0])

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
sort = sorted(A)
# amari = []
# while len(amari) != 1:
#   amari.clear()
#   if 0 in sort: sort.remove(0)
#   for item in sort:
#     if item%sort[0] not in amari:
#       amari.append(item%sort[0])
#   last_sort0 = sort[0]
#   sort = sorted(amari[:])
#   sort.append(last_sort0)

# print(last_sort0-amari[0])

while len(sort) != 1:
  for i in range(1,len(sort)):
    sort[i] = sort[i]%sort[0]
  sort = [j for j in sorted(sort) if j != 0]

print(sort[0])
### BUGGY CODE ###

C = -(10**9 + 7)


def main():
    N = int(input())
    K = N//2
    A = [int(i) for i in input().split()]
    dp = [[C]*(K+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][0] = 0
        if i != 0:
            dp[i][1] = max(dp[i-1][1], A[i-1])
    for i in range(2, N+1):
        for j in range(2, K+1):
            if dp[i-1][j] == -1 and dp[i-2][j-1] == -1 \
                    and (i < 3 or dp[i-3][j-1] == -1):
                dp[i][j] = -1
            else:
                dp[i][j] = max(dp[i][j], dp[i-1][j],
                               dp[i-2][j-1] + A[i-1])
                if i > 2:
                    dp[i][j] = max(dp[i][j], dp[i-3][j-1] + A[i-1])
    print(dp[N][K])
    # print(*dp, sep="\n")


if __name__ == '__main__':
    main()


### FIXED CODE ###

C = -(10**15 + 7)


def main():
    from collections import defaultdict
    N = int(input())
    K = N//2
    A = [int(i) for i in input().split()]
    dp = defaultdict(lambda: C)
    for i in range(N+1):
        dp[i, 0] = 0
        if i != 0:
            dp[(i, 1)] = max(dp[i-1, 1], A[i-1])
    for i in range(2, N+1):
        for j in range(i//2-1, (i+1)//2 + 1):
            if j < 0:
                continue
            # A_i(1-index)でj個選ばなければいけない
            dp[i, j] = max(dp[i, j], dp[i-2, j-1] + A[i-1],
                           dp[i-3, j-1] + A[i-1], dp[i-4, j-1] + A[i-1])
    print(max(dp[N, K], dp[N-1, K], dp[N-2, K]))
    # for i in range(N+1):
    #     for j in range(K+1):
    #         print("{:>4}".format(dp[i, j] if dp[i, j] != C else "C"),
    #               end=" " if j != K else "\n")


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

S = input()
 
 
def solve():
    # print(S)
    diff = ord("a")
 
    head = 0
    while head < len(S):
        tail = head + 1
        while tail <= len(S):
            # print(S[head:tail])
            table = [0 for _ in range(abs(ord("z") - ord("a")) + 1)]
            for j in range(len(S[head:tail])):
                # print("\t{}".format(S[head:tail][j:j+1]))
                index = ord(S[head:tail][j:j+1]) - diff
                table[index] += 1
                # print(table[index], len(S[head:tail]), table[index] / len(S[head:tail]))
                if len(S[head:tail]) >= 2 and table[index] / len(S[head:tail]) > 0.5:
                    # print("hit:" + S[head:tail])
                    # print(head + 1, tail)
                    return head + 1, tail
 
            tail += 1
        head += 1
 
    # print("no hit")
    return -1, -1
 
res = solve()
print(res[0], res[1])

### FIXED CODE ###

S = input()

def solve2():
    head = 0
    tail = 2
    while head < len(S):
        # print(S[head:tail])
        # print("\t" + S[head:tail][0:1])
        # print("\t" + S[head:tail][1:2])
        if S[head:tail][0:1] == S[head:tail][1:2]:
            return head + 1, tail
        head += 1
        tail += 1

    head = 0
    tail = 3
    while head < len(S):
        # print(S[head:tail])
        # print("\t" + S[head:tail][0:1])
        # print("\t" + S[head:tail][1:2])
        # print("\t" + S[head:tail][2:3])
        if S[head:tail][0:1] == S[head:tail][2:3]:
            return head + 1, tail
        head += 1
        tail += 1

    return -1, -1

res = solve2()
print(res[0], res[1])
### BUGGY CODE ###

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 行列のDPを持つ　縦軸がa
N, Ma, Mb = lr()
INF = 5000
limit = N * 10 + 1
dp = [[INF] * limit for _ in range(limit)]
dp[0][0] = 0
for _ in range(N):
    a, b, c = lr()
    used = set()
    for i in range(limit):
        if i < a:
            continue
        for j in range(limit):
            if j < b:
                continue
            # 商品は１個しか買えない            
            if (i-a, j-b) not in used:
                if dp[i][j] > dp[i-a][j-b] + c:
                    used.add((i, j))
                    dp[i][j] = dp[i-a][j-b] + c

answer = INF
for i in range(1, limit):
    if i % Ma != 0:
        continue
    for j in range(1, limit):
        if j % Mb != 0:
            continue
        if i // Ma == j // Mb:
            if dp[i][j] < answer:
                answer = dp[i][j]

print(answer if answer != INF else -1)
# 10

### FIXED CODE ###

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 行列のDPを持つ　縦軸がa
N, Ma, Mb = lr()
INF = 5000
limit = N * 10 + 1
dp = [[INF] * limit for _ in range(limit)]
dp[0][0] = 0
for _ in range(N):
    a, b, c = lr()
    used = set()
    for i in range(limit):
        if i < a:
            continue
        for j in range(limit):
            if j < b:
                continue
            # 商品は１個しか買えない            
            if (i-a, j-b) not in used:
                if dp[i][j] > dp[i-a][j-b] + c:
                    used.add((i, j))
                    dp[i][j] = dp[i-a][j-b] + c

answer = INF
for i in range(1, limit):
    if i % Ma != 0:
        continue
    for j in range(1, limit):
        if j % Mb != 0:
            continue
        if i // Ma == j // Mb:
            if dp[i][j] < answer:
                answer = dp[i][j]

print(answer if answer != INF else -1)
# 10
### BUGGY CODE ###

import collections
N = int(input())

ab = [list(map(int, input().split())) for i in range(N-1)]

eda = [set() for i in range(N)]

for a, b in ab:
    eda[a-1].add(b)
    eda[b-1].add(a)
max_e = 0
for i in range(N-1):
    max_e = max(max_e, len(eda[i]))
id = 0
for i in range(N):
    if len(eda) == max_e:
        id = i

ans = [1]*(N-1)
q = collections.deque()
q.append(id)
print(max_e)
ans = [[0]*N for i in range(N)]
eda2 = [{i for i in range(1, max_e+1)} for j in range(N)]
g = [set() for i in range(N)]

for a, b in ab:
    g[a-1].add(b-1)
    g[b-1].add(a-1)
while(q):
    x = q.popleft()
    for y in g[x]:
        for z in eda2[x]:
            ans[x][y] = z
            ans[y][x] = z
            eda2[x].remove(z)
            eda2[y].remove(z)
            break

        q.append(y)
        g[y].remove(x)
for a, b in ab:
    print(ans[a-1][b-1])


### FIXED CODE ###

import collections
import sys
input = sys.stdin.readline
N = int(input())
ab = [list(map(int, input().split())) for i in range(N-1)]
eda = [set() for i in range(N)]
for a, b in ab:
    eda[a-1].add(b)
    eda[b-1].add(a)
max_e = 0
for i in range(N-1):
    max_e = max(max_e, len(eda[i]))
id = 0
for i in range(N):
    if len(eda[i]) == max_e:
        id = i

q = collections.deque([(id, 0)])
print(max_e)
d = dict()
for a, b in ab:
    d[(a-1, b-1)] = 0
    d[(b-1, a-1)] = 0
eda2 = [set() for j in range(N)]

g = [set() for i in range(N)]

for a, b in ab:
    g[a-1].add(b-1)
    g[b-1].add(a-1)


while(q):
    x, color = q.popleft()
    i = 1
    for y in g[x]:
        if i == color:
            i += 1
        d[(x, y)] = i
        d[(y, x)] = i
        g[y].remove(x)
        q.append((y, i))
        i += 1

for a, b in ab:
    print(d[(a-1, b-1)])
### BUGGY CODE ###

import bisect
n = int(input())
a = sorted(list(map(int,input().split())))
b = sorted(list(map(int,input().split())))
c = sorted(list(map(int,input().split())))
ansum = 0
def stat(array,par):
    return bisect.bisect_right(array,par)

for A in a:
    index = stat(b,A)
    for B in b[index:]:
        indexC = stat(c,B)
        ansum += max(0,n-indexC)
print(ansum)


### FIXED CODE ###

import bisect
n = int(input())
a = sorted(list(map(int,input().split())))
b = sorted(list(map(int,input().split())))
c = sorted(list(map(int,input().split())))
d = [-1] * n
ansum = 0
def stat(array,par):
    return bisect.bisect(array,par)

for i in range(n):
    indexC = stat(c,b[i])
    d[i] = max(0,n-indexC) 
for i in range(n-1):
    d[n-i-2] += d[n-i-1]
for A in a:
    index = stat(b,A)
    if index < n:
        ansum += d[index]
print(ansum)
### BUGGY CODE ###

n,q = map(int, input().split())
s = input()
li = set()
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        li.add(i+1)

for i in range(q):
    l, r = map(int, input().split())
    ans = 0
    for num in li:
        if l <= num and num+1 <= r:
            ans += 1
    print(ans)

### FIXED CODE ###

n,q = map(int, input().split())
s = input()
li = [0]*(n+1)
for i in range(n):
    if s[i:i+2] == "AC":
        li[i+1] = li[i] + 1
    else:
        li[i+1] = li[i]

for i in range(q):
    l, r = map(int, input().split())
    print(li[r-1] - li[l-1])
### BUGGY CODE ###

N, K = map(int, input().split())
D = set(input())

n = N
while True:
    if set(str(n)) in D:
        print(n)
        break
    n += 1


### FIXED CODE ###

N, K = map(int, input().split())
D = set(input())

n = N
while True:
    if len(set(str(n)) & D) == 0:
        print(n)
        break
    n += 1
### BUGGY CODE ###

import bisect

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

ans = 0
for j in range(len(B)):
    axb = bisect.bisect_left(A, B[j])
    bxc = len(C) - len(C[:bisect.bisect(C, B[j])])
    ans += axb * bxc
print(ans)


### FIXED CODE ###

import bisect
N = int(input())
A = sorted(map(int, input().split()))
B = map(int, input().split())
C = sorted(map(int, input().split()))
print(sum(bisect.bisect_left(A, b) * (N - bisect.bisect(C, b)) for b in B))
### BUGGY CODE ###

def myAnswer(N:int,K:int,P:list) ->  int:
   l =[]
   for i in range(0,N-K+1,1):
      l.append(sum(P[i:i+K]))
   target = l.index(max(l))
   ans = 0
   for t in range(target,target+K):
      total = 0
      for i in range(1,P[t]+1):
         total += i
      ans += total/P[t]

   return ans

def modelAnswer():
   return
def main():
   N,K = map(int,input().split())
   P = list(map(int,input().split()))
   print(myAnswer(N,K,P[:]))
if __name__ == '__main__':
   main()

### FIXED CODE ###

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

ruisekiwa=[0]

for i in range(N):
    ruisekiwa.append(ruisekiwa[i]+(1+p[i])/2)

max_value=0
for i in range(N-K+1):
    tmp=ruisekiwa[i+K]- ruisekiwa[i]
    if(max_value < tmp):
        max_value=tmp
print(max_value)
### BUGGY CODE ###

comp = 0
def m(L, R):
    global comp
    i = j = 0
    while i < len(L) and j < len(R):
        comp += 1
        if L[i] <= R[j]:
            yield L[i]
            i += 1
        else:
            yield R[j]
            j += 1
    comp += len(L) - i + len(R) - j
    while i < len(L):
        yield L[i]
        i += 1
    while j < len(R):
        yield R[j]
        j += 1
def merge(A):
    global comp
    if len(A) == 1:
        return A
    if len(A) == 2:
        comp += 2
        a, b = A
        return A if a < b else (b, a)
    mid = len(A) // 2
    L = merge(A[:mid])
    R = merge(A[mid:])
    A[:] = m(L, R)
    return A

n, *A = map(int, open(0).read().split())
B = merge(A)
print(*B)
print(comp)

### FIXED CODE ###

comp = 0
def m(L, R):
    global comp
    j = 0
    for l in L:
        while j < len(R) and R[j] < l:
            yield R[j]
            j += 1
        yield l
    while j < len(R):
        yield R[j]
        j += 1
    comp += len(L) + len(R)
def merge(A):
    global comp
    if len(A) == 1:
        return A
    if len(A) == 2:
        comp += 2
        a, b = A
        return A if a < b else (b, a)
    mid = len(A) // 2
    A[:] = m(merge(A[:mid]), merge(A[mid:]))
    return A

n, *A = map(int, open(0).read().split())
B = merge(A)
print(*B)
print(comp)
### BUGGY CODE ###

def judge(x):
    if x < 1:
        print('No')
    else:
        print('Yes')

n,k,q = map(int,input().split())
human_list = [k]*n
#print(human_list)
for i in range(q):
    a = int(input())
    human_list = list(map(lambda x: x-1,human_list))
    human_list[a-1] += 1
    #print(human_list)
for i in range(n):
    judge(human_list[i])


### FIXED CODE ###

def judge(x):
    if x < 1:
        print('No')
    else:
        print('Yes')

n,k,q = map(int,input().split())
#human_list = [k]*n
ok_list = [0]*n
for i in range(q):
    a = int(input())
    #human_list = list(map(lambda x: x-1,human_list))
    ok_list[a-1] += 1
    #print(human_list)
ok_list = list(map(lambda x: x+k-q,ok_list))
for i in range(n):
    judge(ok_list[i])
### BUGGY CODE ###

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

inf = 10**18
ans = 1

if 0 in a:
    ans = 0
else:
    sorted(a, reverse=True)
    for i in a:
        ans *= i

print(ans if ans <= inf else -1)


### FIXED CODE ###

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

inf = 10**18
ans = 1

sorted(a, reverse=True)
if 0 in a:
    print(0)
    exit()
else:
    for i in a:
        ans *= i
        if ans > inf:
            print(-1)
            exit()

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

import sys
input = sys.stdin.readline

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

living = N
while(living > 1):
    A = sorted(A)
    if A[N-1] % A[N-2] == 0:
        living -= 1
    A[N-1] = A[N-1] % A[N-2]
    
print(sum(A))


### FIXED CODE ###

import sys
from fractions import gcd
input = sys.stdin.readline

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

f = A[0]
for i in range(1, N):
    f = gcd(f, A[i])
print(f)
### BUGGY CODE ###

import itertools

N = int(input())

def generate_prime_numbers():
    search_range = 150
    search_list = [True for i in range(0, search_range+1)]
    search_list[0] = False
    search_list[1] = False
    search_list[2] = True
    for i in range(2, search_range+1):
        for j in range(i*2, search_range+1, i):
            search_list[j] = False
    prime_numbers = [i for i in range(search_range+1) if search_list[i] == True]
    return prime_numbers[:27]

prime_numbers = generate_prime_numbers()
encoded_strings = []
for i in range(N):
    S = input()
    encoded_string = 1
    for c in S:
        char_to_int = ord(c) - ord('a')
        encoded_string *= prime_numbers[char_to_int]
    encoded_strings.append(encoded_string)
# print(encoded_strings)

ans = 0
for comb in itertools.combinations(encoded_strings, 2):
    if comb[0] == comb[1]:
        ans += 1

print(ans)


### FIXED CODE ###

import itertools
from collections import Counter
import math

N = int(input())

def generate_prime_numbers():
    search_range = 150
    search_list = [True for i in range(0, search_range+1)]
    search_list[0] = False
    search_list[1] = False
    search_list[2] = True
    for i in range(2, search_range+1):
        for j in range(i*2, search_range+1, i):
            search_list[j] = False
    prime_numbers = [i for i in range(search_range+1) if search_list[i] == True]
    return prime_numbers[:27]

def combination(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n-r)

prime_numbers = generate_prime_numbers()
encoded_strings = []
for i in range(N):
    S = input()
    encoded_string = 1
    for c in S:
        char_to_int = ord(c) - ord('a')
        encoded_string *= prime_numbers[char_to_int]
    encoded_strings.append(encoded_string)
# print(encoded_strings)

ans = 0
# for comb in itertools.combinations(encoded_strings, 2):
#     if comb[0] == comb[1]:
#         ans += 1
counter = Counter(encoded_strings)
for i in counter.values():
    if i > 1:
        ans += combination(i, 2)

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

N,M=map(int,input().split())
import copy
a=[0]*M
b=[0]*M
for i in range(M):
    a[i],b[i]=map(int,input().split())
D=[[1]]
def route(D):
    E=[]
    D1=copy.deepcopy(D)
    for j in range(len(D)):
        x=D[j][-1]
        for i in range(M):

            if a[i]==x:
                if not b[i] in D1[j]:
                    D=copy.deepcopy(D1)
                    D[j].append(b[i])
                    E.append(D[j])
            elif b[i]==x:
                if not a[i] in D1[j]:
                    D=copy.deepcopy(D1)
                    D[j].append(a[i])
                    E.append(D[j])
    return E
for i in range(N-1):
    D=copy.deepcopy(route(D))
print(len(D))

    

### FIXED CODE ###

N,M=map(int,input().split())
import copy
a=[0]*M
b=[0]*M
for i in range(M):
    a[i],b[i]=map(int,input().split())
D=[[1]]
def route(D):
    E=[]
    D1=copy.deepcopy(D)
    for j in range(len(D)):
        x=D[j][-1]
        for i in range(M):

            if a[i]==x:
                if not b[i] in D1[j]:
                    D[j]=copy.deepcopy(D1[j])
                    D[j].append(b[i])
                    E.append(D[j])
            elif b[i]==x:
                if not a[i] in D1[j]:
                    D[j]=copy.deepcopy(D1[j])
                    D[j].append(a[i])
                    E.append(D[j])
    return E
for i in range(N-1):
    D=copy.deepcopy(route(D))
print(len(D))