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

import numpy as np
import copy
n, m = [int(i) for i in input().split()]
a=[]
b=[]
for i in range(m):
    x1, y1 = [int(i) for i in input().split()]
    a.append(x1)
    b.append(y1)

ans = 0
while True:
    bridge = np.array([0]*(n-1))
    for i in range(len(a)):
        bridge[a[i]-1:b[i]-1] += 1
    r = bridge.argmax() + 1

    for i,an,bn in zip(range(len(a)),a,b):
        if an <= r <= bn-1:
            a[i]=0
            b[i]=0

    ans += 1
    if len(set(a))==1 and a[0]==0:
        break

print(ans)

### FIXED CODE ###

n, m = [int(i) for i in input().split()]
a=[]
b=[]
for i in range(m):
    x1, y1 = [int(i) for i in input().split()]
    a.append(x1)
    b.append(y1)

c = zip(b,a)
c = sorted(c)
b,a = zip(*c)

#print(a,b)
ans = 0
point=0

for i in range(m):
    if a[i]<point<b[i]:
        continue
    else:
        ans += 1
        point=b[i]-0.5

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

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



Asum=[0]
for i in A:
  if Asum[-1]+i>K:break
  Asum.append(Asum[-1]+i)
    
Bsum=[0]
for i in B:
  if Bsum[-1]+i>K:break
  Bsum.append(Bsum[-1]+i)

maxval=len(Asum)-1

tmp=0
cnt=0
lenB=len(Bsum)
lenA=len(Asum)
for i in range(lenA):
  for j in range(lenB):
    j=tmp+j
    if Asum[-i-1]+Bsum[j]>K:
      maxval=max(maxval,len(Asum)-1-i+j-1)
      tmp=j
      break
    elif j==lenB-1:
      maxval=max(maxval,lenA-1-i+j)
      break
print(maxval)


### FIXED CODE ###

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

Asum=[0]
for i in A:
  if Asum[-1]+i>K:break
  Asum.append(Asum[-1]+i)
import numpy as np
Asum=np.array(Asum)
Bsum=[0]
for i in B:
  if Bsum[-1]+i>K:break
  Bsum.append(Bsum[-1]+i)
Bsum=np.array(Bsum)

maxval=len(Asum)-1

tmp=0
lenB=len(Bsum)
lenA=len(Asum)
for i in range(lenA):
  if lenA-1-i+lenB<maxval:break
  for j in range(lenB):
    j=tmp+j
    if Asum[-i-1]+Bsum[j]>K:
      maxval=max(maxval,len(Asum)-1-i+j-1)
      tmp=j
      break
    elif j==lenB-1:
      maxval=max(maxval,lenA-1-i+j)
      break
print(maxval)
### BUGGY CODE ###

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

high = 10**18
low = 0

while high-low > 1:
    mid = (high+low)//2
    tmp = mid
    for i in range(K):
        tmp = tmp//A[i]*A[i]
    if tmp <= 2:
        low = mid
    else:
        high = mid
    L = low
    
high = 10**18
low = 0

while high-low > 1:
    mid = (high+low)//2
    tmp = mid
    for i in range(K):
        tmp = tmp//A[i]*A[i]
    if tmp >= 2:
        high = mid
    else:
        low = mid
    S = high

if S <= L:
    print(S,L)
else:
    print(-1)

### FIXED CODE ###

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

high = 10**18
low = 0

while high-low > 1:
    mid = (high+low)//2
    tmp = mid
    for i in range(K):
        tmp = tmp//A[i]*A[i]
    if tmp <= 2:
        low = mid
    else:
        high = mid
    L = low
    
high = 10**18
low = 0

while high-low > 1:
    mid = (high+low)//2
    tmp = mid
    for i in range(K):
        tmp = tmp//A[i]*A[i]
    if tmp >= 2:
        high = mid
    else:
        low = mid
    S = high

if S <= L:
    print(S,L)
else:
    print(-1)
### BUGGY CODE ###

from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
if N == 1:
    print('1')
else:
    g = gcd(A[0],A[1])
    lcm = (A[0]*A[1]) // g
    for x in A[2:]:
        lcm = (lcm * x) // gcd(lcm,x)
    print(sum((lcm//x) for x in A)%1000000007)

### FIXED CODE ###

from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
if N == 1:
    print('1')
else:
    g = gcd(A[0],A[1])
    lcm = (A[0]*A[1]) // g
    for x in A[2:]:
        lcm = (lcm * x) // gcd(lcm,x)
    print(sum((lcm//x) for x in A)%1000000007)
### BUGGY CODE ###

s=raw_input()
l=len(s)

str=""
i=0
LSUM=[0]
cnt=0
while i<l:
	x=s[i]
	if x=="A":
		str+="A"
		i+=1
		cnt=LSUM[-1]+1
	elif i+1<l and s[i]=="B" and s[i+1]=="C":
		str+="D"
		i+=2
		cnt=LSUM[-1]
	else:
		str+="X"
		i+=1
		cnt=0
	LSUM.append( cnt )

LSUM=LSUM[1:]

ans=0
for i,x in enumerate(str):
	if x=="D":
		ans+=LSUM[i]

print ans

### FIXED CODE ###

s=raw_input()
l=len(s)

i=0
cnt=0
ans=0
while i<l:
	x=s[i]
	if x=="A":
		i+=1
		cnt+=1
	elif i+1<l and s[i]=="B" and s[i+1]=="C":
		i+=2
		ans+=cnt
	else:
		i+=1
		cnt=0


print ans
### BUGGY CODE ###

from bisect import *
n = int(input())
x = list(map(int, input().split()))
l = int(input())
q = int(input())

dp_plus = [[0]*(n+1) for i in range(30)]
dp_minus = [[0]*(n+1) for i in range(30)]

for i in range(n):
    now = x[i]
    reach = now + l
    dp_plus[0][i+1] = bisect_right(x, reach)

for i in range(n):
    now = x[i]
    reach = now - l
    dp_minus[0][i+1] = bisect_left(x, reach) + 1



for i in range(29):
    for j in range(1, n+1):
        dp_plus[i+1][j] = dp_plus[i][dp_plus[i][j]]
        dp_minus[i+1][j] = dp_minus[i][dp_minus[i][j]]


for _ in range(q):
    a, b = map(int, input().split())
    ans = 1
    if a < b:
        for i in range(29, -1, -1):
            if dp_plus[i][a] < b:
                a = dp_plus[i][a]
                ans += pow(2, i)

    else:
        for i in range(29, -1, -1):
            if dp_minus[i][a] > b:
                a = dp_minus[i][a]
                ans += pow(2, i)

    print(ans)


### FIXED CODE ###

from bisect import *
n = int(input())
x = list(map(int, input().split()))
l = int(input())
q = int(input())

dp_plus = [[0]*(n+1) for i in range(30)]
dp_minus = [[0]*(n+1) for i in range(30)]

for i in range(n):
    now = x[i]
    reach = now + l
    dp_plus[0][i+1] = bisect_right(x, reach)

for i in range(n):
    now = x[i]
    reach = now - l
    dp_minus[0][i+1] = bisect_left(x, reach) + 1



for i in range(29):
    for j in range(1, n+1):
        dp_plus[i+1][j] = dp_plus[i][dp_plus[i][j]]
        dp_minus[i+1][j] = dp_minus[i][dp_minus[i][j]]


for _ in range(q):
    a, b = map(int, input().split())
    ans = 1
    if a < b:
        for i in range(29, -1, -1):
            if dp_plus[i][a] < b:
                a = dp_plus[i][a]
                ans += pow(2, i)

    else:
        for i in range(29, -1, -1):
            if dp_minus[i][a] > b:
                a = dp_minus[i][a]
                ans += pow(2, i)

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

from heapq import heappush, heappop

INT_MAX = 10 ** 9


def main():
  n, m = map(int, input().split())
  ab = (map(int, input().split()) for i in range(m))
  
  g = [[0] * (n+1) for i in range(n+1)]
  gp = [INT_MAX] * (n+1)
  gf = [0] * (n+1)
  
  for a, b in ab:
    g[a][b] = 1
    g[b][a] = 1
  
  h = [(0, 1, 1)]
  
  while h:
    if all(0 < i < INT_MAX for i in gf[2:]):
      break
    p, b, a = heappop(h)
    if p < gp[b]:
      gp[b] = p
      gf[b] = a
    else:
      continue
    for x in range(1, n+1):
      if g[b][x]:
        heappush(h, (p + 1, x, b))
  
  r = gf[2:]
  s = 'Yes' if all(0 < i < INT_MAX for i in r) else 'No'
  print(s)
  if s == 'Yes':
    for i in r:
      print(i)
  
  
  
if __name__ == '__main__':
  main()


### FIXED CODE ###

from collections import deque

def main():
  n, m = map(int, input().split())
  ab = (map(int, input().split()) for i in range(m))
  
  ggg = [[] for i in range(n+1)]
  ff = [0] * (n+1)
  
  for a, b in ab:
    ggg[a].append(b)
    ggg[b].append(a)
    
  qq = deque()
  qq.append(1)
  ff[1] = 1
  
  while qq:
    a = qq.popleft()
    for b in ggg[a]:
      if not ff[b]:
        ff[b] = a
        qq.append(b)
  
  rr = ff[2:]
  y = all(rr)
  
  print('Yes' if y else 'No')
  if y:
    for r in rr:
      print(r)

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

def judge(numlist):
    if numlist[2] + numlist[0] == 2 * numlist[1]:
        return False
    else:
        return True

N = int(input())
S = list(input())
R = []
G = []
B = []

for i in range(N):
    if S[i] == 'R':
        R.append(i)
    elif S[i] == 'G':
        G.append(i)
    else:
        B.append(i)

RGcombs = []

for i in R:
    for j in G:
        if i < j:
            RGcombs.append([i,j])
        else:
            RGcombs.append([j,i])

RGBcombs = []

for comb in RGcombs:
    for k in B:
        if k < comb[0]:
            RGBcombs.append([k]+comb)
        elif k > comb[1]:
            RGBcombs.append(comb+[k])
        else:
            RGBcombs.append([comb[0],k,comb[1]])

ans = 0
for satcomb in RGBcombs:
    if judge(satcomb):
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())
r = 0
g = 0
b = 0

for i in range(N):
    if S[i] == 'R':
        r += 1
    elif S[i] == 'G':
        g += 1
    else:
        b += 1

allcnt = r * g * b

sub = 0
for i in range(N):
    for j in range(i+1,N):
        if S[i] == S[j]:
            None
        else:
            k = 2*j-i
            if k >= N or S[i] == S[k] or S[j] == S[k]:
                None
            else:
                sub += 1

print(allcnt - sub)
### BUGGY CODE ###

def seven(n):
    ans=0
    for i in range(n):
        ans*=10
        ans+=7
    return ans
k=int(input())
if(k%2==0):
    print(-1)
else:
    x=1
    while(1):
        if(seven(x)%k==0):
            print(x)
            break
        else:
            x+=1

### FIXED CODE ###

K = int(input())

t = 7
for i in range(K):
    if t % K == 0:
        print(i + 1)
        break
    t = (t * 10 + 7) % K
else:
    print(-1)
### BUGGY CODE ###

N = int(input())

paper = []

for i in range(N):
  ai = int(input())
  if ai in paper:
    paper.remove(ai)
  else:
    paper.append(ai)

print(len(paper))

### FIXED CODE ###

def main():
    N = int(input())

    paper = []
    for i in range(N):
        paper.append(int(input()))

    # TimSortっていうMergeSortの改良版らしい
    paper.sort()

    preNum = paper[0]
    sameNumCount = 1
    ans = 0
    for num in paper[1:]:
        if preNum == num:
            sameNumCount += 1
        else:
            ans += sameNumCount % 2
            preNum = num
            sameNumCount = 1
    # 一番最後の判定
    if paper[-1] == preNum:
        ans += sameNumCount % 2

    print(ans)

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

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

for i in range(m):
    b, c = map(int, input().split())
    for j in range(b):
        cards.append(c)

cards.sort(reverse=True)

print(sum(cards[:n]))

### FIXED CODE ###

import numpy as np
 
n, m = map(int, input().split())
 
cards = list(map(int, input().split()))
cards = np.array(cards, np.int64)
cards.sort()

bc = [list(map(int, input().split())) for _ in range(m)]
bc = np.array(bc, np.int64)

B = bc[:,0]
C = bc[:,1]
 
#並び替えた配列のidxをnparrayで取得
idx = C.argsort()
B = B[idx][::-1]
C = C[idx][::-1]
 
p = 0
for b,c in zip(B,C):
    cards[p:p+b] = np.maximum(cards[p:p+b], c)
    p += b

print(sum(cards))
### BUGGY CODE ###

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
dp=[0]*(n+2)
dp[0]=0
dp[1]=1
for j in range(n):
  if j+1 not in a:
    dp[j+2]=dp[j]+dp[j+1]
    dp[j+2]%=10**9+7
  else:
    dp[j+2]=0
print(dp[j+2]%(10**9+7))

### FIXED CODE ###

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
b=set(a)
dp=[0]*(n+2)
dp[0]=0
dp[1]=1
for j in range(n):
  if j+1 not in b:
    dp[j+2]=(dp[j]+dp[j+1])%(10**9+7)
  else:
    dp[j+2]=0
print(dp[j+2]%(10**9+7))
### BUGGY CODE ###

from fractions import gcd
from functools import reduce
from itertools import combinations

n = int(input())
a = [int(x) for x in input().split()]

b = list(combinations(a, n-1))

gcd_a = [reduce(gcd, list(x)) for x in b]
print(max(gcd_a))


### FIXED CODE ###

from fractions import gcd
from functools import reduce

n = int(input())
a = [int(x) for x in input().split()]

left = [0] * (n + 1)
right = [0] * (n + 1)
for i in range(n):
   left[i+1] = gcd(left[i], a[i])
   right[n-i-1] = gcd(right[n-i], a[n-1-i])

ans = 0
for i in range(n):
   ans = max(ans, gcd(left[i], right[i+1]))
print(ans)
### BUGGY CODE ###

h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
cmap=[input() for _ in range(h)]
from math import ceil
from heapq import heappop,heappush,heapify
dv={'w':0,'n':1,'e':2,'s':3}
seen=[[[0]*4 for _ in range(w)] for _ in range(h)]
todo=[[0,x1,y1,'w'],[0,x1,y1,'n'],[0,x1,y1,'e'],[0,x1,y1,'s']]

heapify(todo)
d=[[0]*w for _ in range(h)]
while todo:
  c,x,y,v=heappop(todo)
  if seen[x][y]==1:continue
  seen[x][y][dv[v]]=1
  d[x][y]=c
  if (x,y)==(x2,y2):
    print(ceil(c))
    #for di in d:
    #  print(di)
    exit()
  #print(c,x,y,v)
  if v=='w':
    if seen[x][y][dv['n']]==0 and cmap[x][y]!='@':heappush(todo,[ceil(c),x,y,'n'])
    if seen[x][y][dv['s']]==0 and cmap[x][y]!='@':heappush(todo,[ceil(c),x,y,'s'])
    while y>0 and cmap[x][y-1]!='@':
      y-=1
      c+=1/k
      if seen[x][y][dv['w']]==0:heappush(todo,[c,x,y,'w'])
  elif v=='e':
    if seen[x][y][dv['n']]==0 and cmap[x][y]!='@':heappush(todo,[ceil(c),x,y,'n'])
    if seen[x][y][dv['s']]==0 and cmap[x][y]!='@':heappush(todo,[ceil(c),x,y,'s'])
    while y<w-1 and cmap[x][y+1]!='@':
      y+=1
      c+=1/k
      if seen[x][y][dv['e']]==0:heappush(todo,[c,x,y,'e'])
  elif v=='n':
    if seen[x][y][dv['w']]==0 and cmap[x][y]!='@':heappush(todo,[ceil(c),x,y,'w'])
    if seen[x][y][dv['e']]==0 and cmap[x][y]!='@':heappush(todo,[ceil(c),x,y,'e'])
    while x>0 and cmap[x-1][y]!='@':
      x-=1
      c+=1/k
      if seen[x][y][dv['n']]==0:heappush(todo,[c,x,y,'n'])
  elif v=='s':
    if seen[x][y][dv['w']]==0 and cmap[x][y]!='@':heappush(todo,[ceil(c),x,y,'w'])
    if seen[x][y][dv['e']]==0 and cmap[x][y]!='@':heappush(todo,[ceil(c),x,y,'e'])
    while x<h-1 and cmap[x+1][y]!='@':
      x+=1
      c+=1/k
      if seen[x][y][dv['s']]==0:heappush(todo,[c,x,y,'s'])

print(-1)
#print(d)


### FIXED CODE ###

from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
cmap=[input() for _ in range(h)]
inf=float('inf')
seen=[[[(inf,inf)]*4 for _ in range(w)] for _ in range(h)]
D=[(-1,0),(0,1),(1,0),(0,-1)]# 上:0, 右:1, 下:2, 左:3
q=deque()
for d in range(4):
  seen[x1][y1][d]=(1,0)
  q.append((x1, y1, d, 1, 0)) # (x, y, 進行方向[d], 移動回数[c], 進行済マス数[k])
while q:
  x,y,d,c,k_=q.popleft()
  # nx, ny: 次の座標
  # nd: 次の進行方向
  # nc: 次の移動回数
  # nk: 次の進行済マス数
  for nd in range(4):
    if nd==d:
      dx,dy=D[nd]
      nk=1 if k_==k else k_+1
      nc=c+1 if k_==k else c
    else:
      dx,dy=0,0
      nk=0
      nc=c+1
    nx=x+dx;ny=y+dy
    if 0<=nx<h and 0<=ny<w and cmap[nx][ny]!='@' and seen[nx][ny][nd]>(nc,nk):
      seen[nx][ny][nd]=(nc,nk)
      if nc==c: # 同一方向に進むケースは次のループで一番はじめに処理する。
        q.appendleft((nx,ny,nd,nc,nk))
      else:
        q.append((nx,ny,nd,nc,nk))
ans=inf
for d in range(4):
  ans=min(ans,seen[x2][y2][d][0])
ans=-1 if ans==inf else ans
print(ans)
### BUGGY CODE ###


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

cnt=0
for i in range(n):
    for j in range(n):
        if abs(i-j)==a[i]+a[j]:
            cnt+=1

print(int(cnt/2))


### FIXED CODE ###

import collections

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

d = dict(collections.Counter([i + A[i] for i in range(N)]))
ans = sum([d.get(j - A[j], 0) for j in range(N)]) # .get()の第２引数は、第１引数がなかった場合に返す値

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

import itertools

N = int(input())
for n in range(1,N+1):
    if n<6: 
        print(0)
        continue
    cnt = 0
    for x,y in itertools.product(list(range(1,int(n**0.5))),repeat=2):
        zz = n - x*x - y*y
        if zz < 1: continue
        for z in range(1,int(zz**0.5)):
            if n == x*x + y*y +z*z + x*y + y*z + z*x:
                cnt += 1
    print(cnt)
    

### FIXED CODE ###

import itertools

N = int(input())
lst = [0]*N
for x,y,z in itertools.product(list(range(1,int(N**0.5))),repeat=3):
    val = x*x + y*y + z*z + x*y + y*z + z*x
    if val <= N:
        lst[val-1] += 1
print(*lst,sep="\n")
### BUGGY CODE ###

n = int(input())
s = input()
count = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    if s[i] != s[j]:  
      for k in range(j+1,n):
        #print(s[i],s[j],s[k])
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i] and j-i != k-j:
          #print(i,j,k)
          count += 1
          #print(s[i],s[j],s[k])
print(count)

### FIXED CODE ###

n = int(input())
s = input()
ans = s.count("R")
ans *= s.count("G")
ans *= s.count("B")
for i in range(n):
    for d in range(n):
        j = i+d
        k = j+d
        if k >= n:
            break
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            ans -= 1

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

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

xlist=[]
ylist=[]
checklist=[]

for i,a in enumerate(alist):
    xlist.append((i+1)+a)
    ylist.append((i+1)-a)
    if ((i+1)-a)>0:
        checklist.append((i+1)-a)

checklist=set(checklist)
output=0
for check in checklist:
    output+= xlist.count(check)*ylist.count(check)

print(output)


### FIXED CODE ###

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

xdic={}
ydic={}

for i,a in enumerate(alist):
    #xlist.append((i+1)+a)
    #ylist.append((i+1)-a)
    tmpx=(i+1)+a
    tmpy=(i+1)-a
    if tmpx in xdic:
        xdic[tmpx]=xdic[tmpx]+1
    else:
        xdic[tmpx]=1
    if tmpy > 0:
        if tmpy in ydic:
            ydic[tmpy]=ydic[tmpy]+1
        else:
            ydic[tmpy]=1

output=0
for y in ydic:
    if y in xdic:
        output+= xdic[y]*ydic[y]

print(output)
### BUGGY CODE ###

n = int(input())
temparr = input()
temparr = temparr.split()
flag = 0 

arr = []
first = 0 
totallen = 0 
for i in  temparr:
    if first == 0 :
        totallen += len(i)
        first = 1 
    else:
        totallen += len(i) - 1 
    if totallen > 19:
        flag = 2
        break
    if "0" in temparr:
        flag = 1 
        break 
    if i == "1" :
        continue
    arr.append(int(i))
if flag == 2:
    print("-1")
elif flag == 1 :
    print("0")
else:
    ans = 1
    arr = sorted(arr)
    arr = arr[::-1]
    for i in arr:
        ans *= i 
        if ans > 1000000000000000000:
            flag = 1 
            break 
    if flag == 0 :
        print(ans)
    else:
        print(-1)
        
        
        


### FIXED CODE ###

n = int(input())
temparr = input()
temparr = temparr.split()
flag = 0 

arr = []
first = 0 
totallen = 0 
arr =[]
arr1 = []
for i in temparr:
    arr1.append(int(i))
arr1 = sorted(arr1)
for i in arr1:
    if i == 0 :
        flag = 1 
        break 
    if i == 1 :
        continue 
    
    if first == 0 :
        totallen += len(str(i))
        first = 1 
    else:
        totallen += len(str(i)) - 1 
    if totallen > 19:
        flag = 2
        break
    arr.append(i)
    
    
if flag == 2:
    print("-1")
elif flag == 1 :
    print("0")
else:
    ans = 1
    arr = sorted(arr)
    arr = arr[::-1]
    for i in arr:
        ans *= i 
        if ans > 1000000000000000000:
            flag = 1 
            break 
    if flag == 0 :
        print(ans)
    else:
        print(-1)
### BUGGY CODE ###

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

count=0

for i in range(a, b+1):
    if i%x==0:
        count +=1

print(count) 

### FIXED CODE ###

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

if a%x==0:
    print(b//x-a//x+1)
else:
    print(b//x-a//x)
### BUGGY CODE ###

N = int(input())
alist = list(map(int, input().split()))
blist = []
for i in range(1,N+1):
    blist.append(alist.index(i)+1)
print(' '.join(map(str, blist)))

### FIXED CODE ###

N = int(input())
alist = list(map(int, input().split()))
blist = []
for i in range(N):
    blist.append([alist[i],i+1])
blist.sort()
for i in range(N):
    print(blist[i][1],end=" ")
### BUGGY CODE ###

from collections import deque

def main():
    N, M = list(map(int, input().split()))
    R = []
    for _ in range(N+1):
        R.append([])
    for _ in range(M):
        x = list(map(int, input().split()))
        R[x[0]].append(x[1])
        R[x[1]].append(x[0])
    
    q = deque()
    s = set()
    r = [0] * (N+1)
    q.append(1)
    while any(q):
        x = q.popleft()
        s.add(x)
        ro = R[x]
        for i in ro:
            if i not in s and i not in q:
                if r[i] == 0:
                    r[i] = x
                q.append(i)
    if len(s) == N:
        print("Yes")
        for i in r[2:]:
            print(i)
    else:
        print("No")

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque

def main():
    N, M = list(map(int, input().split()))
    R = [set() for _ in range(N+1)]
    for _ in range(M):
        x = list(map(int, input().split()))
        R[x[0]].add(x[1])
        R[x[1]].add(x[0])
    
    q = deque()
    #s = set()
    r = [0] * (N+1)
    q.append(1)
    while any(q):
        x = q.popleft()
        #s.add(x)
        ro = R[x]
        for i in ro:
            #if r[i] == 0 and i not in s and i not in q:
            if r[i] == 0: 
                r[i] = x
                q.append(i)
    #if len(s) == N:
    print("Yes")
    print("\n".join(map(str, r[2:])))
    #else:
    #    print("No")

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

A,B=map(int,input().split())
ans=A
for i in range(A+1,B+1):
    ans=ans^i
print(ans)

### FIXED CODE ###

A,B=map(int,input().split())

def func(n):
    ans=0
    if n>0:
        for i in range((n//4)*4,n+1):
            ans ^= i
        return ans
    else:return 0

print(func(A-1)^func(B))
### BUGGY CODE ###

from collections import deque

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

m = [[0 for _ in range(W)] for _ in range(H)]
root = []
for i in range(H):
    # m.append(list(map(lambda x: 0 if x=="#" else 1, input()))）
    for j, c in enumerate(input()):
        if c == "#":
            m[i][j] = 1
            root.append([i, j])

# print(m)
# print(root)

queue = deque(root)
visited = deque(root)
ans = 0
while len(visited) < H*W:
    # print(visited)
    ans += 1
    new_queue = deque([])
    while queue:
        p = queue.popleft()
        for i, j in ([-1, 0], [1, 0], [0, 1], [0, -1]):
            next_p = [p[0] + i, p[1] + j]
            if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
                if not m[next_p[0]][next_p[1]]:
                    m[next_p[0]][next_p[1]] = 1
                    new_queue.append(next_p)
    visited.extend(new_queue)
    queue = new_queue
print(ans)

### FIXED CODE ###

from collections import deque

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

m = [[0 for _ in range(W)] for _ in range(H)]
root = []
for i in range(H):
    # m.append(list(map(lambda x: 0 if x=="#" else 1, input()))）
    for j, c in enumerate(input()):
        if c == "#":
            m[i][j] = 1
            root.append((i, j))

# print(m)
# print(root)

queue = deque(root)
visited = deque(root)
visited_extend = visited.extend
ans = 0
while len(visited) < H*W:
    # print(visited)
    ans += 1
    new_queue = deque([])
    while queue:
        p = queue.popleft()
        for i, j in ([-1, 0], [1, 0], [0, 1], [0, -1]):
            next_p = (p[0] + i, p[1] + j)
            if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
                if not m[next_p[0]][next_p[1]]:
                    m[next_p[0]][next_p[1]] = 1
                    new_queue.append(next_p)
    visited_extend(new_queue)
    queue = new_queue
print(ans)
### BUGGY CODE ###

import numpy as np
import math

n = int(input())
max = 1e+18
ans = 1
a = input().split()

for i in range(n):
    ans *= int(a[i])

if ans > max:
    ans = -1

print(ans)


### FIXED CODE ###

import numpy as np
import math

n = int(input())
max = 1e+18
is_zero = False
ans = 1
a = input().split()

for i in range(n):
    if (int(a[i]) == 0):
        ans = 0
        is_zero = True
        break

if not is_zero:
    for i in range(n):
        ans *= int(a[i])
        if ans > max:
            ans = -1
            break

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

def chk(A,B):
  nL=len(A)
  ans=0
  for i in range(nL):
    if A[i]!=B[i]:
      break
    elif i==nL-1:
      ans=1
  return ans
n=int(input())
s=[sorted(input()) for i in range(n)]
s.sort()
cnt=0
k=0
for i in range(n-1):
  for j in range(i+1,n):
    k=chk(s[i],s[j])
    if k==0:
      break
    else:
      cnt+=k
print(cnt)

### FIXED CODE ###

n=int(input())
A={}
for i in range(n):
  s=str(sorted(input()))
  if s in A.keys():
    A[s]+=1
  else:
    A[s]=1
ans=0
for i in list(A.values()):
  ans+=int(i*(i-1)/2)
print(ans)