Harryxun/stf_run huggingface dataset:
import sys
from collections import defaultdict
readline = sys.stdin.readline

N, M = map(int, readline().split())
G = defaultdict(set)
for v in range(M):
    a, b = map(int, readline().split())
    G[a].add(b)
    G[b].add(a)


def main():

    if M % 2 != 0:
        print(-1)
        return
    ks = []
    for i in G:
        if len(G[i])%2 != 0:
            ks.append(i)
    if len(ks) not in [0, 2]:
        print(-1)
        return
    if len(ks) == 0:
        s=t=1
    else:
        s,t=ks
    v=s
    tr = []
    es = set()
    while True:
        tr.append(v)
        if len(G[v]) == 0:
            break
        u = G[v].pop()
        G[u].remove(v)
        v = u
    tr = tr[::-1]
    tr2 = []
    cc = None
    for (i, t) in enumerate(tr):
        if len(G[t-1]) != 0:
            cc = i
            v = t-1
            while True:
                tr2.append(v+1)
                if len(G[v]) == 0:
                    break
                u = G[v].pop()
                G[u].remove(v)
                v = u
            break
    rs = []
    if cc != None:
        2//0
        ind = 0
        for i in range(cc):
            if ind % 2 == 0:
                print(tr[i+1], tr[i])
            else:
                print(tr[i], tr[i+1])
            ind+=1
        for i in range(len(tr2)-1):
            if ind % 2 == 0:
                print(tr2[i+1], tr2[i])
            else:
                print(tr2[i], tr2[i+1])
            ind+=1
        owari = cc+len(tr2)-1
        nokori = M-owari
        for i in range(nokori):
            i = i + cc
            if ind % 2 == 0:
                print(tr[i+1], tr[i])
            else:
                print(tr[i], tr[i+1])
            ind+=1
    else:
        for i in range(M):
            if i %2 == 0:
                print(tr[i+1], tr[i])
            else:
                print(tr[i], tr[i+1])
    return

if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(10**7)
readline = sys.stdin.readline
def solve(p, v, rs):
    als = G[v]
    cs = g[v]
    c = 0
    for u in als:
        if u in cs:
            c += solve(v, u, rs)
        elif u != p:
            if v < u:
                c += 1
            rs.add((min(u,v), max(u,v)))
    if p == None:
        return
    elif c%2 != 0:
        rs.add((v, p))
        return 0
    else:
        rs.add((p,v))
        return 1

N, M = map(int, readline().split())
if M %2 != 0:
    print(-1)
else:
    G = defaultdict(set)
    for v in range(M):
        a, b = map(int, readline().split())
        G[a].add(b)
        G[b].add(a)

    stack=[1]
    vs = set([1])
    g = defaultdict(set)
    counter = 1
    while True:
        v = stack.pop()
        for u in G[v]:
            if u in vs:
                continue
            vs.add(u)
            g[v].add(u)
            stack.append(u)
            counter += 1
        if counter == N:
            break
    rs = set()
    solve(None,1, rs)
    for r in rs:
        print(r[0], r[1])
import numpy as np
hoge = input()
N,A,B,C,D = list(map(int,hoge.split(" ")))
k = np.abs(B-A)//D
l = np.abs(B-A)%D
times = k + 2 * np.ceil (l/ (D-C))
if times > N-2:
    print("NO")
else:
    print("YES")

### FIXED CODE ###

import numpy as np
import scipy.misc as scm
hoge = input()
hoge = list(map(int,hoge.split(" ")))
N = hoge[0]
P = hoge[1]
A = input()
A = list(map(int,A.split(" ")))
A = np.array(A)

odd = len(A[A %2 == 1])
even = N -odd
perm = 0
if P == 0:
    for i in range(0,odd+1,2):
        perm +=scm.comb(odd,i,1)
else:
    for i in range(1,odd+1,2):
            perm +=scm.comb(odd,i,1)
ans = 2**even * perm
print(ans)
# メモ化再帰
# import math
# import numpy as np
# import copy
# from collections import defaultdict, Counter
# from itertools import product
# from bisect import bisect_left, bisect_right

def s_inpl(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))

N = int(input())
h = inpl()

# 最小化問題なのでINFに初期化
INF = float("inf")
dp = [ INF ] * N

def solve(i):
    # DPの値が更新されていたらそのまま
    if dp[i] < INF:
        return dp[i]

    # 足場0のコストは0
    if i == 0:
        return 0

    # dp[i]の計算
    res = INF
    ## 足場i-1から来た場合
    res = min(res, solve(i-1) + abs(h[i] - h[i-1]))
    ## 足場i-2から来た場合
    if i > 1:
        res = min(res, solve(i-2) + abs(h[i] - h[i-2]))

    # メモ
    dp[i] = res

    return res


print(solve(N-1))

### FIXED CODE ###

import math
import numpy as np
import copy
from collections import defaultdict, Counter
from itertools import product
from bisect import bisect_left, bisect_right

def s_inpl(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))

N = int(input())
h = inpl()

INF = 10e11

# 最小化問題なのでINFに初期化
dp = [ INF for _ in range(100010) ]

# 初期状態
dp[0] = 0

# ループ
for i in range(1, N):
    dp[i] = min(dp[i], dp[i-1] + abs(h[i] - h[i-1]))
    if i > 1:
        dp[i] = min(dp[i], dp[i-2] + abs(h[i] - h[i-2]))

print(dp[N-1])
while True:
        (a, op, b) = input().split()
        a = int(a)
        b = int(b)
        
        if op = '?':
            break
        elif op = '+':
               print(a + b)
        elif op = '-':
               print(a - b)
        elif op = '*':
               print(a * b)
        elif op = '/':
               print(a // b)
      

### FIXED CODE ###

while True:
    (a, op, b) = input().split()
    a = int(a)
    b = int(b)

    if op == '?':
        break
    elif op == '+':
        print(a + b)
    elif op == '-':
        print(a - b)
    elif op == '*':
        print(a * b)
    elif op == '/':
        print(a // b)
from math import ceil
from heapq import heapify, heappop, heappush

N, K, *A = map(int, open(0).read().split())

a = [(-i, i, 1) for i in A]
heapify(a)
while K != 0:
    i, j, k = heappop(a)
    #print(i, j, k)
    t = -a[0][0]
    nk = ceil(j / t)
    t = min(nk - k, K)
    K -= t
    k = nk
    i = -(j / k)
    heappush(a, (i, j, k))
    #print(i, j, k)
print(ceil(heappop(a)[0] * -1))


### FIXED CODE ###

from math import ceil

N, K, *A = map(int, open(0).read().split())

def is_ok(n):
    t = 0
    for a in A:
        if a <= n:
            continue
        t += ceil(a / n) - 1
    return t <= K

ok = 1000000000
ng = 0.0000000001
while abs(ng - ok) > 1:
    m = (ok + ng) // 2
    if is_ok(m):
        ok = m
    else:
        ng = m

print(ceil(ok))
import math

N = int(input())
M = int(input())


def combinations_count(n, r):
    if n <= 1:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = combinations_count(N, 2)
m = combinations_count(M, 2)

print(n+m)

### FIXED CODE ###

import math

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



def combinations_count(n, r):
    if n <= 1:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = combinations_count(N, 2)
m = combinations_count(M, 2)

print(n+m)
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N = int(input())
    xy = [list(map(int,input().split())) for i in range(N)]

    xy = np.array(xy)
    # print(xy)

    diffs = np.expand_dims(xy,axis=1) - np.expand_dims(xy,axis=0)
    md = np.sum(np.abs(diffs),axis=-1)
    res = md.max()

    # print(diffs)
    # print(md)

    print(res)



main()


### FIXED CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N = int(input())
    xy = [list(map(int,input().split())) for i in range(N)]

    z_max = 0
    z_min = 2 * 10 **9

    w_max = - 10 ** 9
    w_min = 10 ** 9

    for i in range(N):
        z = xy[i][0] + xy[i][1]
        w = xy[i][0] - xy[i][1]
        z_max = max(z_max,z)
        z_min = min(z_min,z)
        w_max = max(w_max,w)
        w_min = min(w_min,w)

    res = max(z_max-z_min,w_max-w_min)

    print(res)



main()
import sys
N, M = map(int, input().split())
ok = [True] * (N + 1)
for _ in range(M):
    a = int(sys.stdin.readline())
    ok[a] = False

dp = [0] * (N + 1)
if ok[1]:
    dp[1] = 1
if ok[2]:
    dp[2] = 2
for s in range(3, N + 1):
    if ok[s]:
        dp[s] = dp[s-1] + dp[s-2]
        dp[s] %= 1000000007
    else:
        dp[s] = 0

print(dp[N])

### FIXED CODE ###

import sys
N, M = map(int, input().split())
ok = [True] * (N + 1)
for _ in range(M):
    a = int(sys.stdin.readline())
    ok[a] = False
ans = 0
if N == 1:
    ans = 1
else:
    counts = [0] * (N + 1)
    if ok[1]:
        counts[1] = 1
    if ok[2]:
        counts[2] = counts[1] + 1
    for s in range(3, N + 1):
        if ok[s]:
            count = counts[s-1] + counts[s-2]
            count %= 1000000007
            counts[s] = count
    ans = counts[N]
print(ans)
from math import pi
r=float(raw_input)

print ("{0:6f}{1:6f}").format(r*r*pi, 2*r*pi)

### FIXED CODE ###

from math import pi
r=float(raw_input())
print ("{0:.6f} {1:6f}").format(r*r*pi,2*r*pi)
N, x = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
a = sorted(a)
for i in range(len(a)):
	if x >= a[i]:
		x -= a[i]
		ans += 1
    else:
      break
print(ans)


### FIXED CODE ###

N, x = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
sum = 0
ans = 0
for i in range(len(a) - 1):
    sum += a[i]
    if sum > x:
        break
    else:
        ans += 1
sum += a[N-1]
if sum == x:
    ans += 1
print(ans)
N, K = map(int, input().split())
h = [int(i) for i in input().split()]
h.extend([10**9]*10)
dp = [10**9] * (N+10)

dp[0] = 0

for i in range(N):
    for j in range(1, K+1):
        dp[i+j] = min(dp[i+j], dp[i] + abs(h[i] - h[i+j]))

print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(i) for i in input().split()]
h.extend([10**9]*1000)
dp = [10**9] * (N+1000)
 
dp[0] = 0
 
for i in range(N):
    for j in range(1, K+1):
        dp[i+j] = min(dp[i+j], dp[i] + abs(h[i] - h[i+j]))
 
print(dp[N-1])
import sys
from collections import Counter
p=10**9 +7
n=int(input())
c=[int(i) for i in sys.stdin]
dic = dict()
for i in c:
    if i in dic:
        if dic[i]:
            dic[i] = False
    else:
        dic[i] = True
newline=[]
stack=0
for i in range(n):
  k=c.pop()
  if dic[k]:
    stack=k
    continue
  else:
    if stack!=k:
      newline.append(k)
    stack=k
result=sum([i-1 for i in Counter(newline).values()])%p
if result%2:
  print(pow(2,result//2 +1,p)-1)
else:
  print((pow(2,result-1//2 +1,p)-1)

### FIXED CODE ###

import sys
n=int(input())
c=[int(i) for i in sys.stdin]
x=[0]*(200001)
c.append(0)
x[c[0]]+= 1
num=1
p=10**9 +7
for i in range(1,n):
  if c[i]-c[i-1]:
    x[c[i]]+= num
    x[c[i]]= x[c[i]]%p
  if c[i]-c[i+1]:
    num=x[c[i]]%p
  else:
    num=0
print(num)
n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))

import numpy as np
import bisect

ra=[0]+list(np.cumsum(a))
rb=[0]+list(np.cumsum(b))

ans=0
for i in range(n+1):    
    capa = k - ra[i]
    if ra[i]<0:
        break
    j=bisect.bisect_right(rb,capa)


    ans=max(ans,i-1+j)
            
print(ans)    

### FIXED CODE ###

a=int(input())

print(a + a**2 + a**3)
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
elif K - 1 < len(d[1]):
    print(0)
else:
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
    ans = K * perm(K - 1, len(d[1]))
    root = d[1]
    a = K - 2
    while True:
        children = []
        for i in root:
            if i in d:
                b = len(d[i])
                if a < b:
                    print(0)
                    break
                ans *= perm(a, b)
                children.extend(d[i])
        else:
            if children == []:
                print(ans % mod)
                break
            root = children
            continue
        break

### FIXED CODE ###

N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)
N, M = input().split()
N = int(N)
M = int(M)
p = []
S = []
for i in range(M):
    a, b = input().split()
    a = int(a)
    p.append(a)
    S.append(b)
right = []
wrong = []
for j in range(N):
    right.append(0)
    wrong.append(0)
for k in range(M):
    if S[k] == 'WA' and right[p[k] - 1] == 0:
        wrong[p[k] - 1] += 1
    else if S[k] == 'AC':
        if right[p[k] - 1] == 0:
            right[p[k] - 1] += 1
print(str(sum(right)) + ' ' + str(sum(wrong)))

### FIXED CODE ###

x = input()
y = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
for i in range(26):
    if y[i] == x:
        print(y[i + 1])
A,B = map(int,input().split())
S = input()

if S.count("-") == 1:
    s1,s2 = S.split("-")
    if len(s1) == A:
        if len(s2) == B:
            print("Yes")
    elif len(s1) == A:
        if len(s2) == B:
            print("Yes")
    else:
        print("No")
        sys.exit(0)
else:
    print("No")


### FIXED CODE ###

import re
A,B = list(map(int,input().split()))
S = input()

d = re.compile("\d+")

if (d.match(S[:A])) and S[A] == "-" and d.match(S[A+1:]):
    print("Yes")

else:print("No")
N = int(input())
if N == 1:
  print("Hallo World")
  else:
    print(int(input()) + int(input()))
    
    

### FIXED CODE ###

#! /usr/bin/env python3
# -*- coding: utf-8 -*-
N = int(input())
if N == 1:
    print('Hello World')
else:
    A,B = [int(input()),int(input())]
    print(A +B)
import sys

for line in sys.stdin:
    a,b,c,d,e,f= map(int,line.split())
    z=a*e-b*d
    if(z!=0):
        x=(c*e-b*f)/z
        y=(a*f-c*d)/z
    print("{0:.3f} {1:.3f)".format(x+0,y+0))

### FIXED CODE ###

while(True):
        try:
            a,b,c,d,e,f=map(float,input().split(" "))
            z=a*e-b*d
            if(z!=0):
                x=(c*e-b*f)/z
                y=(a*f-c*d)/z
            print("{:.3f} {:.3f}".format(x+0,y+0))
        except:
            break
from collections import Counter
n=int(input())
x=[]
y=[]
for i in range(n):
  X,Y=map(int,input().split())
  x.append(X)
  y.append(Y)
z=[]
for j in range(n):
  for k in range(j+1,n):
    z.append((x[j]-x[k],y[j]-y[k]))
Z=Counter(z)
m=Z.most_common()[0][1]
print(n-m)


    
    
    


### FIXED CODE ###

from collections import Counter
import sys
n=int(input())
lst=[]
for i in range(n):
  X,Y=map(int,input().split())
  lst.append([X,Y])
lst_2=sorted(lst,key=lambda x: x[0])
lst_3=sorted(lst,key=lambda x: x[1])
z=[]
if n==1:
  print(1)
  sys.exit()
else:
  for j in range(n):
    for k in range(j+1,n):
      z.append((lst_2[j][0]-lst_2[k][0],lst_2[j][1]-lst_2[k][1]))
u=[]
if n==1:
  print(1)
  sys.exit()
else:
  for j in range(n):
    for k in range(j+1,n):
      u.append((lst_3[j][0]-lst_3[k][0],lst_3[j][1]-lst_3[k][1]))
Z=Counter(z)
U=Counter(u)
m=max(Z.most_common()[0][1],U.most_common()[0][1])
print(n-m)
n=raw_input()
a=[]
for i in range(n):
   a.append(int(raw_input()))
print'%d %d %d' % (min(a), max(a), sum(a))

### FIXED CODE ###

n=input()
a=map(int,raw_input().split())
print "%d %d %d" % (min(a), max(a), sum(a))
R,G,B,N = map(int,input().split())
cnt = 0
for r in range((N // R) + 1):
    for g in range((N // G) + 1):
        V = N - (r * R + g * G)
        if V >= o and V % B == 0:
            cnt += 1
print(cnt)


### FIXED CODE ###

R,G,B,N = map(int,input().split())
cnt = 0
for r in range((N // R) + 1):
    for g in range((N - (r * R)) // G + 1):
        V = N - (r * R + g * G)
        if V >= 0 and V % B == 0:
            cnt += 1
print(cnt)
import math
n=int(input())
ans=0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            ans+=gcd(gcd(i,j),k)
print(ans)

### FIXED CODE ###

import math
k = int(input())
ansA, ansB, ansC = 0, 0, 0
for a in range(k):
    ansC += a+1
    for b in range(k-a-1):
        GCDab = math.gcd(a+1, a+b+2)
        ansB += GCDab
        for c in range(k-a-b-2):
            GCDabc = math.gcd(GCDab, a+b+c+3)
            ansA += GCDabc
ans = ansA * 6 + ansB * 6 + ansC
print(ans)
N = int(input())
A = list(map(int,input().split()))
result = [0]*(1000000001)
for a in A:
  result[a] += 1
  result[a-1] += 1
  result[a+1] += 1
print(max(result))

### FIXED CODE ###

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

nums = [0]*(10**5+10)
for a in A:
  nums[a] += 1
  nums[a-1] += 1
  nums[a+1] += 1
print(max(nums))
import math
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = list(set(A))
AA = [a//2 for a in A]
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
l = 1
for i in range(len(AA)):
    l = lcm(l, AA[i])
amari = l % 2
if amari == 1:
    ans = M // l
    print((ans+1)//2)
else:
    print(0)

### FIXED CODE ###


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

def gcd(x, y):
    if x < y:
        x, y = y, x
    while x % y != 0:
        x, y = y, x % y
    return(y)

def lcm(x, y):
    ans = (x * y) // gcd(x, y)
    return(ans)
l = 1
cnt = [0 for i in range(len(A))]
for i in range(len(A)):
    a = A[i]
    l = lcm(l, a)
    count = 0
    while True:
        if a % 2 == 0:
            a //= 2
            count += 1
        else:
            cnt[i] = count
            break
count = cnt[0]
flag = True
for i in range(len(A)):
    if cnt[i] != count:
        flag = False
        break
if flag:
    l = l // 2
    ans = M // l
    print((ans+1)//2)
else:
    print(0)
A, B, C = input().split()

if a < b and b < c:
  print('No')

if a < c and c < b:
  print('Yes')

if b < c and c < a:
  print('Yes')

if b < a and a < c:
  print('No')
  
if c < a and a < b:
  print('Yes')
  
if c < b and b < a:
  print(No)

### FIXED CODE ###

a, b, c = input().split()
if (int(a) < int(c) and int(c) < int(b)) or (int(b) < int(c) and int(c) < int(a)):
  print('Yes')
else:
  print('No')
n,x = map(int,input().split())
L=list(map(int,input().split()))

cnt =0
pos =0
jp=[]
for i in range(n+1):
  if pos<=x:
    cnt +=1
    jp.append(pos)
    pos +=L[i]
  else:
    break

print(cnt)

### FIXED CODE ###

n,x = map(int,input().split())
L=list(map(int,input().split()))
 
cnt =0
pos =0
jp=[]
for i in range(len(L)+1):
  if pos<=x:
    cnt +=1
    jp.append(pos)
    if i<(len(L)):
      pos +=L[i]
    else:
      break
  else:
    break

print(cnt)
import copy
[n,x]=list(map(int,input().split()))
a=list(map(int,input().split()))
a0=copy.copy(a)
ans=0
if a[0]+a[1]>x and a[0]>x:
	a[0]-=a[0]-x
	and+=a[0]-x
		if a[0]+a[1]>x:
			a[1]=0
			ans+=a[1]
	
for i in range(1,n-1):
	if a[i]+a[i+1]>x:
		a[i+1]-=a[i]+a[i+1]-x
		ans+=a[i]+a[i+1]-x
print(ans)

### FIXED CODE ###

import copy
[n,x]=list(map(int,input().split()))
a=list(map(int,input().split()))
a0=copy.copy(a)
ans=0
if a[0]+a[1]>x and a[0]>x:
	ans+=a[0]-x
	a[0]-=a[0]-x
	if a[0]+a[1]>x:
		ans+=a[1]
		a[1]=0	
for i in range(n-1):
	if a[i]+a[i+1]>x:
		ans+=a[i]+a[i+1]-x
		a[i+1]-=a[i]+a[i+1]-x
		
print(ans)
N=int(input())
if(N%1000==0):
  m=(int(N/1000)
else:
  m=(int(N/1000)
change=1000*m-N
print(change)

### FIXED CODE ###

N = int(input())
if (N % 1000 == 0):
    m = (int(N/1000))
else:
    m=(int(N/1000)+1)
change=1000*m-N
print(change)
from fraction import gcd


def main():
  a, b = map(int, input().split())
  print(a * b // gcd(a, b))
  
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

from fractions import gcd


def main():
  a, b = map(int, input().split())
  print(a * b // gcd(a, b))
  
  
if __name__ == "__main__":
  main()
import sys
sys.setrecursionlimit(100000)

n, q = map(int, input().split())
dist = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    dist[a - 1].append(b - 1)
value = []
cnt = [0 for i in range(n)]
for i in range(q):
    p, x = map(int, input().split())
    value.append([p - 1, x])

def dfs(pos, addvalue):
    cnt[pos] += addvalue
    for i in dist[pos]:
        dfs(i, addvalue)

for i in value:
    dfs(i[0], i[1])

for i in cnt:
    print(i, end = " ")

### FIXED CODE ###

from collections import deque

n, q = map(int, input().split())
dist = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    dist[a - 1].append(b - 1)
    # aftercontest対策
    dist[b - 1].append(a - 1)
value = [0 for i in range(n)]

# 1つ目の[1, 10]と2つ目の[1, 10]混ぜても問題なし
for i in range(q):
    p, x = map(int, input().split())
    value[p - 1] += x
#  重複を防ぐ
ignore = [0] * n
ignore[0] = 1

pos = deque([0])
# 上から順に自身のvalueの値を子のvalueに加算していく
# value [100, 10, 1, 0]
# pos.popleft() = 1 → [100, 10 + 100, 1 + 100, 0 + 100]
# pos.popleft() = 2 → [100, 110, 101 + 10, 100 + 10]
while len(pos) > 0:
    u = pos.popleft()
    for i in dist[u]:
        if ignore[i] == 0:
            ignore[i] = 1
            value[i] += value[u]
            pos.append(i)
# 覚える
print(*value)
hon = input()

digit_1 = hon % 10

if digit_1 == 2 or 4 or 5 or 7 or 9:
    print('hon')

elif digit_1 == 0 or 1 or 6 or 8:
    print('pon')

elif digit_1 == 3:
    print("bon")


### FIXED CODE ###

digit_1 = int(input()) % 10

if digit_1 in [2 , 4 , 5 ,7 ,9]:
    print('hon')

elif digit_1 in [0 , 1 , 6 , 8]:
    print('pon')

elif digit_1 == 3:
    print("bon")
n = int(intput())
s = []
for i in range(n):
  tmp = str(input())
  tmp.sort()
  s.append(tmp)

a = [0, 0]
for i in range(2, 10**3):
  x = a[i-1] + (i-1)
  a.append(x)

ans = 0
for _ in list(set(s)):
  ans+= a[s.count(_)]
  
print(ans)

### FIXED CODE ###

alphabet = "abcdefghijklmnopqrstuvwxyz"


n = int(input())
res = dict()
for _ in range(n):
    s = str(input())
    freqency = [0 for _ in alphabet]
    for __ in s:
        freqency[alphabet.index(__)] += 1
    freq = "".join([str(___) for ___ in freqency])
    if freq not in res:
        res[freq] = 1
    else:
        res[freq] += 1

ans = 0
for value in res.values():
    ans += ((value-1)*value)/2
  
print(int(ans))