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


N = int(input())

uvw = []
Nlis = [-1] * N
Ndic = {}

for i in range(N-1):

    u,v,w = map(int,input().split())
    
    if u not in Ndic:
        Ndic[u] = [[v,w]]

    else:
        Ndic[u].append([v,w])

    if v not in Ndic:
        Ndic[v] = [[u,w]]

    else:
        Ndic[v].append([u,w])


ends = set([1])
Q = [1]
Nlis[0] = 0

while len(Q) > 0 and N != 1:

    now = Q.pop(0)

    for nw in Ndic[now]:

        if nw[0] not in ends:

            Q.append(nw[0])
            ends.add(nw[0])

            if nw[1] % 2 == 0:
                Nlis[nw[0]-1] =  Nlis[now-1]

            else:
                Nlis[nw[0]-1] = (Nlis[now-1] + 1) % 2

            Ndic[nw[0]].remove([now,nw[1]])

for i in Nlis:
    print(i)


### FIXED CODE ###


N = int(input())

uvw = []
Nlis = [-1] * N
Ndic = {}

for i in range(N-1):

    u,v,w = map(int,input().split())
    
    if u not in Ndic:
        Ndic[u] = [[v,w]]

    else:
        Ndic[u].append([v,w])

    if v not in Ndic:
        Ndic[v] = [[u,w]]

    else:
        Ndic[v].append([u,w])


ends = set([1])
Q = [1]
Q_cnt = 0
Nlis[0] = 0

while len(Q) > Q_cnt and N != 1:

    now = Q[Q_cnt]
    Q_cnt += 1

    for nw in Ndic[now]:

        if nw[0] not in ends:

            Q.append(nw[0])
            ends.add(nw[0])

            if nw[1] % 2 == 0:
                Nlis[nw[0]-1] =  Nlis[now-1]

            else:
                Nlis[nw[0]-1] = (Nlis[now-1] + 1) % 2

            #Ndic[nw[0]].remove([now,nw[1]])

for i in Nlis:
    print(i)
### BUGGY CODE ###

N = int(input())
a = [int(input()) for i in range(N)]
q = 1
cnt = 0
li = []
for i in range(100001):
    q = a[q-1]
    cnt += 1
    if q == 2:
        print(cnt)
        break
    if q in li:
        print(-1)
        break
    li.append(q)

### FIXED CODE ###

import sys
N = int(input())
a = [int(input()) for i in range(N)]
q = 1
cnt = 0
li = []
for i in range(100001):
    q = a[q-1]
    cnt += 1
    if q == 2:
        print(cnt)
        sys.exit()
print(-1)
### BUGGY CODE ###

a, b, n = map(int, input().split())
if n < b:
    print((a*n)//b)
else:
    ans = -1
    for x in range(b//a, b*2+1):
        tmp = (a*x)//b - a*(x//b)
        if tmp > ans:
            ans = tmp
        elif tmp < ans:
            break
    print(ans)

### FIXED CODE ###

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

def f(x):
    return (a*x)//b-a*(x//b)

if n < b:
    print(f(n))
else:
    print(f(b-1))
### BUGGY CODE ###

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


@njit(i8(i8,i8[:]))
def loop(N,A):
    res = 0
    for i in range(N):
        now = A[i]
        for j in range(N):
            if j == i:
                continue
            if now % A[j] == 0:
                res -= 1
                break
        res += 1
    return res


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

    A = np.array(A)

    res = loop(N,A)

    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)
# from numba import njit,i8


def sieve(N,A,dp):
    for i in range(N):
        now = A[i]
        M = A[-1] // now
        for j in range(2,M+1):
            dp[now*j-1] = False
    return dp


def cnt(N,A,dp):
    skip = 0
    res = 0
    for i in range(N):
        now = A[i]
        if skip == now:
            continue
        if i != N - 1:
            if now == A[i+1]:
                skip = now
                continue
        if dp[now-1]:
            res += 1
    return res


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

    A = sorted(A)
    A = np.array(A)

    dp = np.array([True for i in range(A[-1])])
    # print(dp)
    dp = sieve(N,A,dp)
    # print(dp)

    res = cnt(N,A,dp)

    print(res)



main()
### BUGGY CODE ###

def solve():
  ans = 0
  S = input()
  T = input()
  n,m = len(S),len(T)
  dp = [['']*(m+1) for _ in range(n+1)]
  for i in range(1,n+1):
    for j in range(1,m+1):
      if S[i-1]==T[j-1]:
        dp[i][j] = dp[i-1][j-1]+S[i-1]
      else:
        if len(dp[i-1][j])>len(dp[i][j-1]):
          dp[i][j] = dp[i-1][j]
        else:
          dp[i][j] = dp[i][j-1]
  return dp[-1][-1]
print(solve())

### FIXED CODE ###

S = input()
T = input()

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

import sys
sys.setrecursionlimit(2000000)
N,M,K=map(int,input().split())
F=[set() for i in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    F[a-1].add(b-1)
    F[b-1].add(a-1)
B=[set() for i in range(N)]
for _ in range(K):
    c,d=map(int,input().split())
    B[c-1].add(d-1)
    B[d-1].add(c-1)

def dps(i, j, c):
    s=0
    con=False
    for f in F[j]:
        if f not in c:
            con=True
            c.add(f)
            if f not in F[i] and f not in B[i]:
                s+=1
            s+=dps(i,f,c)
    if not con:
        return 0
    else:
        return s
for i in range(0,N):
    checked=set([i])
    print(dps(i, i, checked), end=" ")

### FIXED CODE ###

N,M,K=map(int,input().split())
A=[];B=[]
for i in range(M):
    a,b=map(int,input().split())
    A.append(a);B.append(b)
C=[];D=[]
for i in range(K):
    c,d=map(int,input().split())
    C.append(c);D.append(d)
f=[set() for i in range(N)]
b=[set() for i in range(N)]
for i in range(M):
    f[A[i]-1].add(B[i]-1)
    f[B[i]-1].add(A[i]-1)
for i in range(K):
    b[C[i]-1].add(D[i]-1)
    b[D[i]-1].add(C[i]-1)
checked=[False for i in range(N)]
class UnionFind:
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
    def root(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.root(self.parents[x])
            return self.parents[x]
    def union(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
    def same(self,x,y):
        return self.root(x)==self.root(y)
    def size(self,x):
        return -self.parents[self.root(x)]
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x<0]
    def group_count(self):
        return len(self.roots())
uf=UnionFind(N)
for i in range(N):
    for people in f[i]:
        uf.union(i,people)
ans=[]
for i in range(N):
    c=uf.size(i)
    bl=0
    for x in b[i]:
        if uf.same(i,x):
            bl+=1
    ans.append(c-bl-1-len(f[i]))
print(*ans)
### BUGGY CODE ###

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

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

probability=[]
for i in range(N):
    num=0
    prob=1/P[i]
    for j in range(1,P[i]+1):
        num+=j*prob
    probability.append(num)

max_num=0
for i in range(N-K+1):
    sum_num=0
    for j in range(i,i+K):
        sum_num+=probability[j]
    if max_num<sum_num:
        max_num=sum_num
print('{:.012f}'.format(max_num))

### FIXED CODE ###

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

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

probability=[]
sums=[0]
total=0
for i in range(N):
    num=0
    prob=1/P[i]
    for j in range(1,P[i]+1):
        num+=j*prob
    probability.append(num)
    total+=num
    sums.append(total)

ans=0
for j in range(N-K+1):
    if ans<sums[j+K]-sums[j]:
        ans=sums[j+K]-sums[j]

print('{:.012f}'.format(ans))
### BUGGY CODE ###

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

temp=[[i+1] for i in range(n)]
tempr=[]
check=[]
for i in range(n-1):
    temp[ab[i][0]-1].append(ab[i][1])
    tempr.append([ab[i][1],ab[i][0]])
    if i >= 1:
        for j in range(i):
            if ab[i][0] == tempr[j][0]:
                temp[tempr[j][1]-1].append(ab[i][1])

ans=[0 for i in range(n)]
for j in range(q):
    for _ in temp[px[j][0]-1]:
        ans[_-1]+=px[j][1]

print(" ".join(map(str,ans)))

### FIXED CODE ###

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

parent=[0 for i in range(n)]
for i in range(n-1):
    parent[ab[i][1]-1]=ab[i][0]
ans=[0 for i in range(n)]
for i in range(q):
    ans[px[i][0]-1]+=px[i][1]
for i in range(1,n):
    if parent[i] != 0:
        ans[i]+=ans[parent[i]-1]


print(" ".join(map(str,ans)))
### BUGGY CODE ###

# # TLEだった
# s = input()
# counter = 0
# for i in range(3, len(s)+1):
#     snum = 0
#     for m in range(i):
#         snum += int(s[m])
#     num = int(s[0:i])
#     if num % 2019 == 0:
#         counter += 1
#     for j in range(1, len(s)-i+1):
#         snum -= int(s[j-1])
#         snum += int(s[j+i-1])
#         if snum % 3 != 0:
#             continue
#         num = int(s[j:j + i])
#         if num % 673 == 0:
#             counter += 1
# print(counter)

import collections


def comb(n):
    return n * (n-1)/2


s = input()
ans = 0
lst_mod = []  # O(N)で回した連続値のmod(2019)の値
for i in range(len(s)):
    mod = int(s[i:]) % 2019
    lst_mod.append(mod)
    if mod == 0:
        ans = + 1

count = list(collections.Counter(lst_mod).values())
for i in range(len(count)):
    ans += comb(count[i])
print(int(ans))


### FIXED CODE ###

import collections


def comb(n):
    return n * (n-1)/2


s = input()
ans = 0
lst_mod = [0]*2019  # O(N)で回した連続値のmod(2019)の値
lst_mod[0] += 1
num, dim = 0, 1
for char in reversed(s):
    num += int(char)*dim
    num %= 2019
    dim *= 10
    dim %= 2019  # サイズを大きくしたくないからmod(2019)を使う
    lst_mod[num] += 1

for mod in lst_mod:
    ans += comb(mod)
print(int(ans))
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
ans = 0
while a:
    b = a[:]
    for i in range(len(a)):
        if i == 0:
            b.remove(a[i])
        elif a[i] > a[i-1]:
            b.remove(a[i])
    ans += 1
    a = b

print(ans)

### FIXED CODE ###

from bisect import bisect_left
from collections import deque

n = int(input())
A = [int(input()) for _ in range(n)]

D = deque([])

for a in A:
    i = bisect_left(D, a)
    if i == 0:
        D.appendleft(a)
    else:
        D[i-1] = a

print(len(D))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
ken = [[]for _ in range(n)]
pairs = []
for i in range(m):
    p,y = map(int,input().split())
    ken[p-1].append(y)
    pairs.append((p,y))

for i in ken:
    if i != []:
        i.sort()

for p,y in pairs:
    x = ken[p-1].index(y) + 1
    print('{:0=6}{:0=6}'.format(p,x))

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
pyi = []
for i in range(m):
    p,y= map(int, input().split())
    pyi.append([p,y,i]) #県番号、誕生年、市番号の順

pyi.sort(key=lambda x: x[1]) #誕生年でソート
pyi.sort(key=lambda x: x[0]) #県番号でソート
#県番号の順番で並びつつも、同県の中では誕生年順になっている

ken = 0 #県番号の初期化
for i in range(m):
    if pyi[i][0] != ken: #新しい県に突入した時
        ken = pyi[i][0] #県番号を更新
        x = 1 #xは同県内での順位を表す
    else: #前と同じ県の時
        x += 1 #同県内の順位は1つ手前の市+1
    pyi[i].append(x) #リストpyiの要素の各リストの末尾に同県内の順位を付け加える

pyi.sort(key=lambda x: x[2]) #出力順に直すために市番号でソート
for i in range(m): #県番号と同県内の順位をゼロ埋めして出力
    print(str(pyi[i][0]).zfill(6)+str(pyi[i][3]).zfill(6))
### BUGGY CODE ###

import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


s = S()
q = I()
queries = SR(q)
for query in queries:
    if query[0] == '1':
        s = s[::-1]
    else:
        _, f, c = query.split()
        if f == '1':
            s = c + s
        else:
            s = s + c
print(s)


### FIXED CODE ###

from collections import deque
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


s = S()
q = I()
queries = SR(q)
que = deque(list(s))
top = True  # 先頭の位置 Trueが左（初期位置）
for query in queries:
    if query[0] == '1':
        top = not(top)
    else:
        _, f, c = query.split()
        if f == '1':
            if top:
                que.appendleft(c)
            else:
                que.append(c)
        else:
            if top:
                que.append(c)
            else:
                que.appendleft(c)
if top:
    print(''.join(list(que)))
else:
    print(''.join(list(que))[::-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)

# ナップザック問題 典型2
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]
V = sum([v for w, v in wv])

dp = [[10**10]*(V+1) for i in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for j in range(0, V+1):
        w, v = wv[i]
        if (j-v) >= 0:
            dp[i+1][j] = min([dp[i][j], dp[i][j-v]+w])
        else:
            dp[i+1][j] = dp[i][j]

ans = 0
for i in range(0, V+1):
    if dp[N][i] <= W:
        ans = i

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

# ナップザック問題 典型2
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]
V = sum([v for w, v in wv])

dp = [[10**10]*(V+1) for i in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for j in range(0, V+1):
        w, v = wv[i]
        if (j-v) >= 0:
            dp[i+1][j] = min([dp[i][j], dp[i][j-v]+w])
        else:
            dp[i+1][j] = dp[i][j]

ans = 0
for i in range(0, V+1):
    if dp[N][i] <= W:
        ans = i

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

k=int(input())

# mod k で考える
mod=k

for i in range(1,k+2):
    if mod>7*int(str(1)*i):
        continue
    else:
        mod = 7 * int(str(1) * i) % k
        if mod == 0:
            print(i)
            exit()

print(-1)

### FIXED CODE ###

k=int(input())

cur=0
for i in range(k+2):
    cur=(cur*10+7)%k
    if cur==0:
        print(i+1)
        exit()

print(-1)
### BUGGY CODE ###

import bisect

N = int(input())
L = [int(input()) for _ in range(N)]
Q = [L[0]]

for l in L[1:]:
    r = bisect.bisect_left(Q, l)
    if r == 0:
        Q.insert(0, l)
    else:
        Q[r-1] = l
print(len(Q))


### FIXED CODE ###

from collections import deque
import bisect

N = int(input())
L = [int(input()) for _ in range(N)]
Q = deque()
Q.append(L[0])

for l in L[1:]:
    r = bisect.bisect_left(Q, l)
    if r == 0:
        Q.appendleft(l)
    else:
        Q[r-1] = l
print(len(Q))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
import sys
sys.setrecursionlimit(10 ** 5+1)
# import numpy as np
# import IPython

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


N, M = ds_in()

to_par = {i: [] for i in range(1, N+1)}
to_chi = {i: [] for i in range(1, N+1)}
con_list = []
for _ in range(N - 1 + M):
    a, b = ds_in()
    to_par[b].append(a)


def find_all_parents(child, par_dict):
    """
    child : int
    """
    all_parents = []
    for p in to_par[child]:
        all_parents.append(p)
        if p in par_dict.keys():
            all_parents.extend(par_dict[p])
        else:
            all_parents.extend(find_all_parents(p, par_dict))
    all_parents = list(set(all_parents))
    return all_parents


parents_dict = {}
for i in range(1, N+1):
    parents_dict[i] = find_all_parents(i, parents_dict)
# parents_dict = {i: find_all_parents(i) for i in range(1, N+1)}

ans = {i: 0 for i in range(1, N+1)}
for child in range(1, N+1):
    par_cand = to_par[child]
    all_par = []
    for p in par_cand:
        all_par.extend(parents_dict[p])
    all_par = list(set(all_par))
    for p in par_cand:
        if p not in all_par:
            ans[child] = p
            break

for i in range(1, N+1):
    print(ans[i])


# IPython.embed()


### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
# import sys
# sys.setrecursionlimit(10 ** 5+1)
import numpy as np
# import IPython

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


N, M = ds_in()

child = {i+1: [] for i in range(N)}
parent = {i+1: [] for i in range(N)}
inflow = {i+1: 0 for i in range(N)}
for _ in range(N+M-1):
    a, b = ds_in()
    child[a].append(b)
    parent[b].append(a)
    inflow[b] += 1

candidates = []
for i, j in inflow.items():
    if j == 0:
        candidates.append(i)

sorted_edges = []
while len(sorted_edges) < N:
    par = candidates.pop()
    sorted_edges.append(par)
    for chi in child[par]:
        inflow[chi] -= 1
        if inflow[chi] == 0:
            candidates.append(chi)


sorted_index = np.zeros(N+1, dtype=int)
sorted_index[sorted_edges] = np.arange(N)

for i in range(1, N+1):
    if i == sorted_edges[0]:
        print(0)
    else:
        print(parent[i][np.argmax(sorted_index[parent[i]])])
### BUGGY CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import deque
import sys
def main(H, W, C, D, S):
    INF = 10**6
    dist = [[INF] * W for _ in range(H)]
    dist[D[0]][D[1]] = 0
    q = deque([D])
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
                if dist[ni][nj] > d:
                    dist[ni][nj] = d
                    q.append((ni, nj))
        for ni in range(i - 2, i + 2 + 1, 1):
            if not(0 <= ni < H): continue
            dni = dist[ni]
            sni = S[ni]
            for nj in range(j - 2, j + 2 + 1, 1):
                if 0 <= nj < W and sni[nj] == '.':
                    if dni[nj] > d + 1:
                        dni[nj] = d + 1
                        q.append((ni, nj))

    ans = dist[C[0]][C[1]]
    print(ans if ans < INF else -1)


if __name__ == '__main__':
    input = sys.stdin.readline
    H, W = map(int, input().split())
    C = tuple(map(lambda x: int(x) - 1, input().split()))
    D = tuple(map(lambda x: int(x) - 1, input().split()))
    S = [list(input().rstrip()) for _ in range(H)]
    main(H, W, C, D, S)


### FIXED CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import deque
import sys
def main(H, W, C, D, S):
    INF = 10**6
    dist = [[INF] * W for _ in range(H)]
    di, dj = D
    dist[di][dj] = 0
    q = deque([(di, dj, 0)])
    while q:
        i, j, d = q.popleft()
        if d > dist[i][j]: continue
        for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
                if dist[ni][nj] > d:
                    dist[ni][nj] = d
                    q.appendleft((ni, nj, d))
        for ni in range(i - 2, i + 2 + 1, 1):
            if not(0 <= ni < H): continue
            dni = dist[ni]
            sni = S[ni]
            for nj in range(j - 2, j + 2 + 1, 1):
                if 0 <= nj < W and sni[nj] == '.':
                    if dni[nj] > d + 1:
                        dni[nj] = d + 1
                        q.append((ni, nj, d + 1))

    ans = dist[C[0]][C[1]]
    print(ans if ans < INF else -1)


if __name__ == '__main__':
    input = sys.stdin.readline
    H, W = map(int, input().split())
    C = tuple(map(lambda x: int(x) - 1, input().split()))
    D = tuple(map(lambda x: int(x) - 1, input().split()))
    S = [list(input().rstrip()) for _ in range(H)]
    main(H, W, C, D, S)
### BUGGY CODE ###

#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import copy

N, K = list(map(int, sys.stdin.readline().rstrip().split()))
data = []
for _ in range(N):
    A, B = list(map(int, sys.stdin.readline().rstrip().split()))
    # print(A)
    # print(bin(A)[2:])
    data.append([list(reversed(bin(A)[2:])), B])

ans = 0


def lower(x, y):
    if(len(x) > len(y)):
        return False
    for xx, yy in zip(x, y):
        if (xx == "1" and yy == "0"):
            return False
    else:
        return True


Nstr = list(reversed(bin(K)[2:]))
subNstrs = [Nstr]
for i in range(len(Nstr)):
    if Nstr[i] == "0":
        continue
    subNstr = copy.deepcopy(Nstr)
    subNstr[i] = "0"
    for j in range(i):
        subNstr[j] = "1"
    subNstrs.append(subNstr)


for subNstr in subNstrs:
    subans = 0
    for A, B in data:
        # print(A, subNstr, lower(A, subNstr))
        if(lower(A, subNstr)):
            subans += B
    # print(subNstr, subans)
    ans = max(subans, ans)

print(ans)

exit(0)


### FIXED CODE ###

#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import copy

N, K = list(map(int, sys.stdin.readline().rstrip().split()))
data = []
for _ in range(N):
    A, B = list(map(int, sys.stdin.readline().rstrip().split()))
    data.append([A, B])

ans = 0


def lower(x, y):
    if(x > y):
        return False
    # print(bin(x), bin(y), bin(x|y), bin((x | y) ^ y))
    if((x | y) ^ y) == 0:
        return True
    else:
        return False


Nstr = list(reversed(bin(K)[2:]))
subNs = [K]
for i in range(len(Nstr)):
    if Nstr[i] == "0":
        continue
    subNstr = copy.deepcopy(Nstr)
    subNstr[i] = "0"
    for j in range(i):
        subNstr[j] = "1"

    realstr = ""
    for s in reversed(subNstr):
        realstr += s
    subNs.append(int(realstr, 2))


for subNstr in subNs:
    subans = 0
    for A, B in data:
        # print(A, subNstr, lower(A, subNstr))
        if(lower(A, subNstr)):
            subans += B
    # print(subNstr, subans)
    ans = max(subans, ans)

print(ans)

exit(0)
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in range(1000):
    p = '00' + str(i)
    k = -3
    for j in range(N):
        if p[k] == S[j]:
            k += 1
            if k == 0:
                ans += 1
                break
print(ans)

### FIXED CODE ###

N = int(input())
t = input()
S = []
for i in range(N):
    S.append(t[i])
import copy
ans = 0
f = []
for i in range(10):
    if str(i) in S:
        f.append(str(i))
while len(f) > 0 and len(S) > 2:
    k = S.pop(0)
    if k in f:
        f.remove(k)
        s = []
        for j in range(10):
            if str(j) in S:
                s.append(str(j))
        T = copy.deepcopy(S)
        while len(s) > 0 and len(T) > 1:
            l = T.pop(0)
            if l in s:
                s.remove(l)
                for i in range(10):
                    if str(i) in T:
                        ans += 1
                        
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    count = 0
    lists =[]
    count_dict = {}

    for i in range(n):
        input_data = ''.join(sorted(input()))
        if input_data in lists:
            if input_data not in count_dict.keys():
                count_dict[input_data] = 1
            count = count + count_dict[input_data]
            count_dict[input_data] = count_dict[input_data] + 1
        else:
            lists.append(input_data)

    print(count)


if __name__ == '__main__' :
    main()

### FIXED CODE ###

from collections import Counter

n = int(input())
count = 0
lists =[]
count_dict = Counter()

for i in range(n):
    input_data = ''.join(sorted(input()))
    if input_data in count_dict:
        count += count_dict[input_data]
        count_dict[input_data] += 1
    else:
        count_dict[input_data] = 1

print(count)