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

n = int(input())

list = [1,2,3,4,5,6,7,8,9]

for i in range(n):
  x = list[0]
  mod_x = x%10
 # print(i,"番目　",x)
  list.pop(0)
  if mod_x != 0:
    list.append(10*x + (x%10) -1)
    
  list.append(10*x + (x%10))
  
  if mod_x != 9:
    list.append(10*x + (x%10) + 1)

print(x)


### FIXED CODE ###

import queue
n = int(input())
q = queue.Queue()
for i in range(9):
    q.put(i+1)
for i in range(n):
  x = q.get()
  mod_x, mul_x = x%10, 10*x
  if mod_x != 0: q.put(mul_x+mod_x-1)
  q.put(mul_x+mod_x)
  if mod_x != 9: q.put(mul_x+mod_x+1)
print(x)
### BUGGY CODE ###

# N:人数, K:初期ポイント, Q:クイズ数
N, K, Q = map(int,input().split())
points = [K] * N

def not_ans(li):
    return li -1

for i in range(Q):
    anser = int(input())-1
    points = list(map(not_ans,points))
    points[anser] += 1
    
for y in range(N):
    if points[y] < 1:
        print('No')
    else:
        print('Yes')


### FIXED CODE ###

# N:人数, K:初期ポイント, Q:クイズ数
N, K, Q = map(int,input().split())

s = K-Q

points = [s] * N

for _ in range(Q):
    ans = int(input())
    points[ans-1] += 1

for p in points:
    print('Yes' if p>0 else 'No')
### BUGGY CODE ###

n,k = map(int,input().split())
lis = list(map(int,input().split()))
ans = [10 ** 9 for i in range(n+5)]
ans[0] = 0
for i in range(n):
    for step in range(1,k+1):
        try:
            ans[i+step] = min(ans[i+step],ans[i] + abs(lis[i+step]-lis[i]))
        except:
            continue
print(ans[n-1])

### FIXED CODE ###

n,k = map(int,input().split())
lis = list(map(int,input().split()))

dp = [10 ** 10 for i in range(n+k+1)]

dp[0] = 0
for i in range(n):
    for j in range(1,min(n-i,k+1)):
        dp[i+j] = min(dp[i+j],dp[i]+abs(lis[i+j]-lis[i]))
print(dp[n-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(500000)
input = sys.stdin.readline
N = int(input()); MOD=pow(10,9)+7
G = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1
  G[a].append(b);G[b].append(a)
#print(G)
ans = 0

def dfs(v,p): #自分と親
  global ans #ansをGlobal変数として宣言
  res = 1 #戻り値。vを含めた部分木のサイズ。自分の分で最初は1
  ts = [] #vから生えている部分木のリスト
  for u in G[v]:
    if u == p:
      continue
    t = dfs(u,v) #uの部分木のサイズが戻り値
    res += t
    ts.append(t)
  if p != -1: #根以外なら親側の部分木が存在する。
    ts.append(N-res)
  now = pow(2,N-1,MOD) - 1 #自分以外を決めるのが2^(N-1)通り。自分以外が全部0が1通り。
  for x in ts:
    now -= pow(2,x,MOD) - 1 #各部分木に一個以上黒がある場合の数。全通り - 全部白
  ans = (ans+now)%MOD
  return res #vを含めた部分木のサイズ

dfs(0,-1)
ALL = pow(2,N,MOD)
#print(ans,ALL)
ans = ans*pow(ALL,MOD-2,MOD)%MOD #フェルマーの小定理より1/ALL = ALL^(MOD-2)
print(ans)
           

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)
input = sys.stdin.readline
N = int(input()); MOD=pow(10,9)+7
G = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1
  G[a].append(b);G[b].append(a)
#print(G)
ans = 0

def dfs(v,p): #自分と親
  global ans #ansをGlobal変数として宣言
  res = 1 #戻り値。vを含めた部分木のサイズ。自分の分で最初は1
  ts = [] #vから生えている部分木のリスト
  for u in G[v]:
    if u == p:
      continue
    t = dfs(u,v) #uの部分木のサイズが戻り値
    res += t
    ts.append(t)
  if p != -1: #根以外なら親側の部分木が存在する。
    ts.append(N-res)
  now = pow(2,N-1,MOD) - 1 #自分以外を決めるのが2^(N-1)通り。自分以外が全部0が1通り。
  for x in ts:
    now -= pow(2,x,MOD) - 1 #各部分木に一個以上黒がある場合の数。全通り - 全部白
  ans = (ans+now)%MOD
  return res #vを含めた部分木のサイズ

dfs(0,-1)
ALL = pow(2,N,MOD)
#print(ans,ALL)
ans = ans*pow(ALL,MOD-2,MOD)%MOD #フェルマーの小定理より1/ALL = ALL^(MOD-2)
print(ans)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
s = [["X"] * (W+2)] + [["X"] + list(input()) + ["X"] for _ in range(H)] + [["X"] * (W+2)]

DH = [1, 0, -1, 0]
DW = [0, 1, 0, -1]

ans = 0
def bfs(start):
	global ans
	que = deque([start])
	visited = [[False for _ in [0]*(W+2)] for _ in [0]*(H+2)]
	visited[start[0]][start[1]] = True
	#cur = s[start[0]][start[1]]
	while que:
		label = que.pop()
		h, w = label[0], label[1]
		if s[start[0]][start[1]] != s[h][w] and W*start[0]+start[1] < W*h+w:
			ans += 1
		for dh, dw in zip(DH, DW):
			if s[h][w] == ".":
				if s[h+dh][w+dw] == "#" and visited[h+dh][w+dw] == False:
					que.appendleft([h+dh, w+dw])
					visited[h+dh][w+dw] = True
			elif s[h][w] == "#":
				if s[h+dh][w+dw] == "." and visited[h+dh][w+dw] == False:
					que.appendleft([h+dh, w+dw])
					visited[h+dh][w+dw] = True


	del que, visited
	return

for i in range(1, H+1):
	for j in range(1, W+1):
		bfs([i, j])

print(ans)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
s = ["X" * (W+2)] + ["X" + input() + "X" for _ in range(H)] + ["X" * (W+2)]
visited = [[-1 for _ in range(W+2)] for _ in range(H+2)]

DH = [1, 0, -1, 0]
DW = [0, 1, 0, -1]

ans = 0
def bfs(start, num):
	global ans
	dot, sharp = 0, 0
	que = deque([start])
	#visited = [[False for _ in [0]*(W+2)] for _ in [0]*(H+2)]
	visited[start[0]][start[1]] = num
	#cur = s[start[0]][start[1]]
	while que:
		label = que.pop()
		h, w = label[0], label[1]
		if s[h][w] == ".":
			dot += 1
		elif s[h][w] == "#":
			sharp += 1
		#if s[start[0]][start[1]] != s[h][w] and W*start[0]+start[1] < W*h+w:
			#ans += 1
		for dh, dw in zip(DH, DW):
			if s[h][w] == ".":
				if s[h+dh][w+dw] == "#" and visited[h+dh][w+dw] == -1:
					que.appendleft([h+dh, w+dw])
					visited[h+dh][w+dw] = num
			elif s[h][w] == "#":
				if s[h+dh][w+dw] == "." and visited[h+dh][w+dw] == -1:
					que.appendleft([h+dh, w+dw])
					visited[h+dh][w+dw] = num
	#del que, visited
	return dot*sharp

k = 0
for i in range(1, H+1):
	for j in range(1, W+1):
		if visited[i][j] == -1:
			ans += bfs([i, j], k)

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

import math
n,p = map(int,input().split())
dum = math.ceil(p**(1/n))
for i in range(dum,-1,-1):
    if p%(i**n) == 0:
        print(i)
        break

### FIXED CODE ###

n,p = map(int,input().split())
dum = round(p**(1/n))
for i in range(dum,-1,-1):
    if p%(i**n) == 0:
        print(i)
        break
### BUGGY CODE ###

N, W = map(int, input().split())
goods = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i, item in enumerate(goods):
    i += 1
    for w in range(1, W+1):
        if w < item[0]:
            dp[i][w] = dp[i-1][w]
        else:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-item[0]] + item[1])

print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
goods = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i, item in enumerate(goods):
    i += 1
    for w in range(1, W+1):
        if w < item[0]:
            dp[i][w] = dp[i-1][w]
        else:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-item[0]] + item[1])

print(dp[N][W])
### BUGGY CODE ###

import sys
import itertools as it
input = sys.stdin.readline

N, M, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

AS = list(it.accumulate(A))
BS = list(it.accumulate(B))
AS.insert(0,0)
BS.insert(0,0)
max = 0
for i in range(N+1):
    a = AS[i]
    if a > K:
        continue
    j = M
    while j < M + 1:
        b = BS[j]
        if a + b <= K:
            if max < i + j:
                max = i + j
            break
        j -= 1

print(max)

### FIXED CODE ###

import sys
import itertools as it
input = sys.stdin.readline

N, M, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

AS = list(it.accumulate(A))
BS = list(it.accumulate(B))
AS.insert(0,0)
BS.insert(0,0)
max = 0
for i in range(N+1):
    a = AS[i]
    if a > K:
        continue
    if max - i > 0:
        j = max - i
    else:
        j = 0
    while j < M + 1:
        b = BS[j]
        if a + b > K:
            break
        if max < i + j:
            max = i + j
        j += 1

print(max)
### BUGGY CODE ###

import sys

fin = sys.stdin.readline
N, M = [int(elem) for elem in fin().split()]
conditions = [tuple(int(elem) for elem in fin().split()) for _ in range(M)]

current_set = set(range(1, 100001))
for l, r in conditions:
    new_set = set(range(l, r+1))
    current_set = new_set & current_set

print(len(current_set))


### FIXED CODE ###

import sys

fin = sys.stdin.readline
N, M = [int(elem) for elem in fin().split()]
conditions = [tuple(int(elem) for elem in fin().split()) for _ in range(M)]

l_list = [x[0] for x in conditions]
r_list = [x[1] for x in conditions]

print(max(0, min(r_list) - max(l_list) + 1))
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    a = [LI() for _ in range(m)]
    e = collections.defaultdict(list)
    r = [0] * n
    f = [False] * n
    for l,r,d in a:
        e[l-1].append((r-1,d))
        e[r-1].append((l-1,-d))
        f[r-1] = False

    b = ['s'] * n
    def g(i,c):
        if f[i] and c != 's':
            return False
        if b[i] != 's':
            if c == 's':
                return True
            return b[i] == c
        if c == 's':
            c = 0
        b[i] = c
        for r,d in e[i]:
            if not g(r,c+d):
                return False
        return True

    for i in range(n):
        if not g(i,'s'):
            return 'No'
    return 'Yes'


print(main())





### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    e = [[] for _ in range(n)]
    if m > 0:
        for _ in range(m):
            l,r,d = LI()
            e[l-1].append((r-1,d))
            e[r-1].append((l-1,-d))

    b = [None] * n

    for i in range(n):
        if not b[i] is None:
            continue
        b[i] = 0
        q = [i]
        qi = 0
        nq = []
        while True:
            if len(q) == qi:
                if not nq:
                    break
                q = nq
                qi = 0
                nq = []
            j = q[qi]
            qi += 1
            c = b[j]
            for r,d in e[j]:
                if b[r] is None:
                    b[r] = c+d
                    nq.append(r)
                else:
                    if b[r] != c+d:
                        return 'No'

    return 'Yes'


print(main())
### BUGGY CODE ###

H,W = map(int, input().split())

A = [["" for _ in range(W)] for _ in range(H)]

stack = []
for i in range(H):
    tmp = list(input())
    for j in range(W):
        A[i][j] = tmp[j]
        if tmp[j] == "#":
            stack.append((i,j))

ans = 0
flag = False
if stack:
    flag = True
while flag:
    ans += 1
    #print(ans, stack)
    flag = False
    new_stack = []
    while stack:
        a,b = stack.pop() # 取り出す
        # A[a][b]の隣接マスについて調べる
        if a != 0: # 上
            if A[a-1][b] == ".": # 白の場合
                A[a-1][b] = "#"
                new_stack.append((a-1,b))
        if a != H-1: # 下
            if A[a+1][b] == ".": # 白の場合
                A[a+1][b] = "#"
                new_stack.append((a+1,b))
        if b != 0: # 左
            if A[a][b-1] == ".": # 白の場合
                A[a][b-1] = "#"
                new_stack.append((a,b-1))
        if b != W-1: # 右
            if A[a][b+1] == ".": # 白の場合
                A[a][b+1] = "#"
                new_stack.append((a,b+1))
    stack = new_stack
    if stack:
        flag = True
    else:
        ans -= 1 

print(ans)
        






### FIXED CODE ###

from collections import deque

def main():
    H,W = map(int, input().split())

    A = [[a for a in input()] for _ in range(H)]
    #stack = deque([(i, j) for i in range(H) for j in range(W) if A[i][j]=="#"])
    stack = [(i, j) for i in range(H) for j in range(W) if A[i][j]=="#"]
    ans = 0
    flag = False
    if stack:
        flag = True
    while flag:
        ans += 1
        flag = False
        #new_stack = deque()
        new_stack = []
        for a,b in stack:
        #while stack:
            #a,b = stack.pop() # 取り出す
            # A[a][b]の隣接マスについて調べる
             # 上
            if a != 0 and A[a-1][b] == ".": # 白の場合
                    A[a-1][b] = "#"
                    new_stack.append((a-1,b))
             # 下
            if a != H-1 and A[a+1][b] == ".": # 白の場合
                    A[a+1][b] = "#"
                    new_stack.append((a+1,b))
            # 左
            if b != 0 and A[a][b-1] == ".": # 白の場合
                    A[a][b-1] = "#"
                    new_stack.append((a,b-1))
            # 右
            if b != W-1 and A[a][b+1] == ".": # 白の場合
                    A[a][b+1] = "#"
                    new_stack.append((a,b+1))
        stack = new_stack
        if stack:
            flag = True
        else:
            ans -= 1 

    print(ans)
            


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

s = input()
k = int(input())
sub = set()
for i in range(0,len(s)):
    j = 1
    while i+j<=len(s):
        sub.add(s[i:i+j])
        j = j + 1
ans = list(sub)
ans.sort()
print(ans[k-1])

### FIXED CODE ###

s = input()
k = int(input())
sub = set()
for i in range(0,len(s)):
    j = 1
    while i+j<=len(s) and j<=5:
        sub.add(s[i:i+j])
        j = j + 1
ans = list(sub)
ans.sort()
print(ans[k-1])
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    import numpy as np
    from collections import Counter

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

    tmp = np.array(list(c.values()))
    l1= tmp*(tmp-1)//2
    l2= (tmp-1)*((tmp-1)-1)//2

    for a in A:
        r = list(c).index(a)
        sum = np.sum(l1) + l2[r] -l1[r]
        print(int(sum))
if __name__ == '__main__':
    main()


### FIXED CODE ###

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

import collections 
c=collections.Counter(A)
sum=0
for i in c:
  sum+=c[i]*(c[i]-1)//2  
for a in A:
  print(sum - c[a]*(c[a]-1)//2 + (c[a]-1)*(c[a]-2)//2)
### BUGGY CODE ###

def main():
    s = list(input())
    ln = len(s)

    abc = ["A", "B", "C"]
    bca = ["B", "C", "A"]

    ans = 0
    for i in range(ln - 2):
        if s[i:i+3] == abc:
            s[i:i+3] = bca
            ans += 1
            j = i - 1
            while j >= 0 and s[j:j+3] == abc:
                s[j:j+3] = bca
                ans += 1
                j -= 1

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

s = input()

s = s.replace("BC", "D")

ans = 0
a_cnt = 0
for e in s:
    if e == "A":
        a_cnt += 1

    elif e == "D":
        ans += a_cnt

    else:
        a_cnt = 0

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

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [1] * (M+1)
dpleft = [0] * (M)
MOD = 10 ** 9 + 7
ndp = [1] * (M+1)
for n in range(N):
    for m in range(M):
        if S[n] == T[m]:
            ndp[m+1] = (ndp[m] + dp[m+1]) % MOD
            dpleft[m] = dp[m+1]
        else:
            ndp[m+1] = (ndp[m] + dpleft[m]) % MOD
        dp[m] = ndp[m]
    dp[-1] = ndp[-1]
print(dp[-1])

### FIXED CODE ###

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
dp = [1] * (M+1)
dpleft = [0] * (M)
MOD = 10 ** 9 + 7
ndp = [1] * (M+1)
for n in range(N):
    for m in range(M):
        if S[n] == T[m]:
            ndp[m+1] = ndp[m] + dp[m+1]
            dpleft[m] = dp[m+1]
        else:
            ndp[m+1] = ndp[m] + dpleft[m]
    dp = ndp[:]
print(dp[-1] % MOD)
### BUGGY CODE ###

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

dp = [-1] * N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        dp[n] = min([abs(A[n] - A[n - k - 1]) + dp[n - k - 1] for k in range(min(K, n))])
print(dp[-1])

### FIXED CODE ###

import sys

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

dp = [0] + [None] * (N - 1)
for n, a in enumerate(A):
    if n:
        l = max(0, n - K)
        dp[n] = min(abs(a - a2) + d for a2, d in zip(A[l : n], dp[l : n]))

print(dp[-1])
### BUGGY CODE ###

H, W = map(int, input().split())
S = [int(input()) for _ in range(W)]
    
floor = list(range(0,H+1))
 
if S.count(1) >0:
	floor[1]=0
	floor[2]=1
if S.count(2) >0:
    floor[2]=0
 
teiou = [0]*H
for i in range (0, H+1):
	if S.count(i) >  0:
		teiou[i] = 1
    
for i in range (3, H+1):
		floor[i]=floor[i-2]*(1-teiou[i-2])+floor[i-1]*(1-teiou[i-1])
print(floor[H]%(10**9+7))

### FIXED CODE ###

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

A = []

for i in range (0, M):
	A.append(int(input()))


if N == 1:
	print(1)
	exit()
elif N ==2:
	if len(A) ==1:
		print(1)
	else:
		print(2)
	exit()

DP = [0]*N

if A.count(1)==0:
	DP[0] = 1

if A.count(2)==0:
	if A.count(1)==0:
		DP[1] = 2
	else:
		DP[1] = 1

for i in range (0, M):
	DP[A[i]-1] = -1

for i in range (0, 2):
	if DP[i] == -1:
		DP[i] = 0

for i in range (2, N):
	if DP[i] ==-1:
		DP[i] = 0
	else:
		DP[i] = DP[i-1] + DP[i-2]

print(DP[-1]%(1000000007))
### BUGGY CODE ###

from collections import Counter
def divisor(n):
    i = 1
    l = []
    while i * i <= n:
        if n%i == 0:
            l.append(i)
            l.append(n//i)
        i += 1
    l = list(set(l))
    return l   

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

arr_1=[]
for i in a:
    arr_1.append(divisor(i))

arr_2=sum(arr_1,[])
arr_3=Counter(arr_2)
ans=0
for d,c in arr_3.items():
    if c>=n-1 and d>=ans:
        ans=d
print(ans)       

### FIXED CODE ###

from fractions import gcd

n=int(input())
a_1=list(map(int,input().split()))
a_2=list(reversed(a_1))
l=[0]
r=[0]

for i in range(n):
    l.append(gcd(l[i],a_1[i]))  

for i in range(n):    
    r.append(gcd(r[i],a_2[i]))
    
r=list(reversed(r))

m=[]
for i in range(n):
   m.append(gcd(l[i],r[i+1])) 

print(max(m))
### BUGGY CODE ###

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

graph1 = [[] for _ in range(n)]
graph2 = [[] for _ in range(n)]

for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph1[u].append(v)


# def dfs(v0, v, k):
#     if k == 0:
#         graph2[v0].append((1, v))
#         return
#
#     for i in range(len(graph1[v])):
#         dfs(v0, graph1[v][i][1], k-1)
#
# for i in range(n):
#     dfs(i, i, 3)
#     # print(graph1[i])

for i in range(n):
    q = [(i, 3)]
    idx = 0
    while True:
        if idx == len(q):
            break
        v, c = q[idx]
        idx += 1
        if c == 0:
            graph2[i].append(v)
            continue
        for j in graph1[v]:
            q.append((j, c-1))



# for i in range(n):
#     print(i)
#     for _, v in graph1[i]:
#         print(" ->", v)
#
#
for i in range(n):
    graph2[i] = list(set(graph2[i]))
# print()
# for i in range(n):
#     print(graph2[i])


s, t = map(int, input().split())
s -= 1
t -= 1


from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    NextCost = 1
    while heap:
        cost,thisNode = heappop(heap)
        for NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
    # dist = [costs to nodes]

inf = float('inf')
dist = dijkstra(graph2, n, s)
if dist[t] == inf:
    print(-1)
else:
    print(dist[t])



### FIXED CODE ###

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

graph1 = [[] for _ in range(n*3)]

for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph1[u*3+0].append(v*3+1)
    graph1[u*3+1].append(v*3+2)
    graph1[u*3+2].append(v*3+0)

s, t = map(int, input().split())
s -= 1
t -= 1
s = s*3
t = t*3

from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    NextCost = 1
    while heap:
        cost,thisNode = heappop(heap)
        for NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
    # dist = [costs to nodes]

inf = float('inf')
dist = dijkstra(graph1, n*3, s)
if dist[t] == inf:
    print(-1)
else:
    print(dist[t]//3)
### BUGGY CODE ###

s = input()
m = int(input())
q_list = [list(input().split()) 
          for nesya in range(m)]
n = 0
for q in q_list:
  if q[0] == '1':
    n += 1
  else:
    f = n + int(q[1])
    if f%2 == 1:
      s = q[2] + s
    else:
      s = s + q[2]
if n%2 == 1:
  s = s[::-1]
print(s)

### FIXED CODE ###

from collections import deque
#入力
s = input()
m = int(input())
q_list = [list(input().split()) 
          for nesya in range(m)]
d = deque(s)
n = 0
for q in q_list:
  if q[0] == '1':
    n += 1
  else:
    if (n%2 == 0 and q[1] == '1') or (n%2 == 1 and q[1] == '2'):
      d.appendleft(q[2])
    else:
      d.append(q[2])
ans = ''.join(d)
if n%2 == 0:
  print(ans)
else:
  print(ans[::-1])
### BUGGY CODE ###

n, m = map(int, input().split())
a, b = map(int, input().split())
k = set(range(a, b+1))
for i in range(m - 1):
    a, b = map(int, input().split())
    k = k.intersection(set(range(a, b+1)))
print(len(k))

### FIXED CODE ###

n, m = map(int, input().split())
L = set()
R = set()
for i in range(m):
    l, r = map(int, input().split())
    L.add(l)
    R.add(r)
if min(R) >=  max(L):
    num = min(R) - max(L) + 1
else:
    num = 0
print(num)
### BUGGY CODE ###

n, w = list(map(int, input().split()))
items = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * (w + 1) for _ in range(n + 1)]
for i in range(n):
    for sum_w in range(w + 1):
        if (sum_w - items[i][0]) >= 0:  # i番目の商品を選択
            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - items[i][0]] + items[i][1])

        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])

print(dp[n][w])


### FIXED CODE ###

def main():
    n, w = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(n)]

    dp = [0] * (w + 1)
    for wi, vi in wv:
        for sum_w in range(w, wi - 1, -1):
            v = dp[sum_w - wi] + vi
            if dp[sum_w] < v:
                dp[sum_w] = v

    print(dp[w])


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


def main():
  from collections import Counter
  N = int(input())
  S = [input() for _ in range(N)]

  tmp = []
  d={}
  for s in S:
    x = Counter(s)
    if x in tmp:
      d[tmp.index(x)] += 1
    else:
      tmp.append(x)
      d[tmp.index(x)] = 1 
      
  cnt = 0
  for v in d.values():
    if v == 1:
      continue
    if v == 2:
      cnt += 1
    elif v == 3:
      cnt += v
    else:
      cnt += sum(list(range(1,v)))

  print(cnt)
if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  N = int(input())
  S = [input() for _ in range(N)]

  d = {}
  for i, s in enumerate(S):
    x = "".join(sorted(s))
    if x in d:
      d[x] += 1
    else:
      d[x] = 1
  
  cnt = 0
  for v in d.values():
    if v == 1:
      continue
    if v == 2:
      cnt += 1
    elif v == 3:
      cnt += v
    else:
      cnt += sum(list(range(1,v)))

  print(cnt)
if __name__ == "__main__":
  main()