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

def main():
    from collections import deque
    N = int(input())
    G = [[] for _ in range(N)]
    edge = {}
    ans_key = []
    for i in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edge[(a-1, b-1)] = -1
        ans_key.append((a-1, b-1))
    max_g = max(len(g) for g in G)

    def bfs(s, max_g):
        dist = [-1 for _ in range(N)]
        color = [{i+1 for i in range(max_g)} for _ in range(N)]
        que = deque()
        que.append(s)
        dist[s] = 0
        while que:
            u = que.popleft()
            for v in G[u]:
                if dist[v] != -1:
                    continue
                dist[v] = dist[u] + 1
                que.append(v)
                c = color[u].pop()
                color[v].discard(c)
                if u < v:
                    edge[(u, v)] = c
                else:
                    edge[(v, u)] = c
            if all(i != -1 for i in edge.values()):
                return
    bfs(0, max_g)
    print(max_g)
    for k in ans_key:
        print(edge[k])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    G = [[]*N for _ in range(N)]
    edge_color = {}
    key_ = []
    for _ in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edge_color[(a-1, b-1)] = -1
        key_.append((a-1, b-1))
    from collections import deque
    deg_max = 0
    for g in G:
        deg_max = max(deg_max, len(g))

    G_color = ['WHITE' for _ in range(N)]
    G_distance = [float('inf') for _ in range(N)]
    G_parent = ['NIL' for _ in range(N)]

    def bfs(s):
        G_color[s] = 'GRAY'
        G_distance[s] = 0
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            if G_parent[u] == 'NIL':
                now_color = 1
            else:
                now_color = (edge_color[(G_parent[u], u)] + 1) % deg_max
            for v in G[u]:
                if G_color[v] == 'WHITE':
                    G_color[v] = 'GRAY'
                    G_distance[v] = G_distance[u] + 1
                    G_parent[v] = u
                    Q.append(v)
                    edge_color[(u, v)] = now_color % deg_max
                    now_color += 1
            G_color[u] = 'BLACK'
    bfs(0)
    print(deg_max)
    for k in key_:
        print(edge_color[k]+1)


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

N,W = map(int,input().split())
k,l = 0,0
lv = [0] * N
lw = [0] * N
for i in range(N):
    lw[i],lv[i] = map(int,input().split())
V = sum(lv)
dp = [[float("inf") for i in range(V+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for sv in range(V):
        if sv-lv[i] < 0:
            dp[i+1][sv] = dp[i][sv]
            k +=1
        else:
            dp[i+1][sv] = min(dp[i][sv],(dp[i][sv-lv[i]]+lw[i]))
            l += 1
a = V

while a >= 0:
    if dp[-1][a] <= W:
        print(a)
        a = -1
    else:
        a -= 1


### FIXED CODE ###

N,W = map(int,input().split())
dp = [[0 for i in range(W+1)] for j in range (N+1)]

for i in range(N):
    w,v = map(int,input().split())
    for sw in range(W+1):
        if sw < w:
            dp[i+1][sw] = dp[i][sw]
        else:
            dp[i+1][sw] = max((dp[i][sw]),(dp[i][sw-w]+v))
print(dp[-1][-1])
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N, T = map(int, input().split())
    ab = [tuple(map(int, input().split())) for i in range(N)]
    ab.sort(key=lambda x: x[0])
    t = ab[-1][0]
    dp = [-1]*(T+t+1)
    dp[0] = 0
    for a, b in ab:
        for i in range(T+t, 0, -1):
            if i >= a:
                if dp[i-a] >= 0 and i - a < T:
                    dp[i] = max(dp[i], dp[i-a] + b)
    ans = max(dp)
    print(ans)


main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N, T = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(N)]
    ab.sort(key=lambda x: (x[0], x[1]))
    dp = [-1 for i in range(T*2 + 1)]
    dp[0] = 0
    for a, b in ab:
        for i in range(T*2, 0, -1):
            if i >= a:
                if dp[i-a] >= 0 and i - a < T:
                    dp[i] = max(dp[i], dp[i-a] + b)

    for i in range(1, T*2+1):
        dp[i] = max(dp[i], dp[i-1])
    ans = dp[-1]

    ab.sort(key=lambda x: x[1])
    tmp = ab.pop()
    dp = [-1 for i in range(T)]
    dp[0] = 0
    for a, b in ab:
        for i in range(T-1, 0, -1):
            if i >= a:
                if dp[i-a] >= 0:
                    dp[i] = max(dp[i], dp[i-a] + b)

    for i in range(1, T):
        dp[i] = max(dp[i], dp[i-1])
    ans = max(ans, tmp[1] + dp[-1])

    # print(dp)
    print(ans)


main()
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l = sorted(l)
sum = 0
for i in range(len(l)):
    for j in range(i + 1, len(l)):
        for k in range(j + 1, len(l)):
            if l[k] < l[i] + l[j]:
                sum += 1
print(sum)

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(len(l)):
    for j in range(i + 1, len(l)):
        ans += max(bisect.bisect_left(l, l[i] + l[j])-j-1, 0)
print(ans)
### BUGGY CODE ###

import sys
from collections import defaultdict
from collections import deque

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

graph = defaultdict(list)

for _ in range(m):
    a, b = map(lambda x: int(x), input().split())
    graph[a].append(b)
    graph[b].append(a)

q = deque([1])
dist = [0] * (n + 1)
dist[1] = 0

while q:
    if max(dist) > 2:
        break
    node = q.popleft()
    after = graph[node]

    for a in after:
        q.append(a)
        if a == n:
            dist[a] = dist[node] + 1
            break
        else:
            dist[a] = dist[node] + 1

print("POSSIBLE" if dist[n] == 1 or dist[n] == 2 else "IMPOSSIBLE")

### FIXED CODE ###

import sys
from collections import defaultdict
from collections import deque

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

graph = defaultdict(list)

for _ in range(m):
    a, b = map(lambda x: int(x), input().split())
    graph[a].append(b)
    graph[b].append(a)

q = deque([1])
dist = [0] * (n + 1)
dist[1] = 0
curr = 0

while q and curr <= 2:
    node = q.popleft()
    after = graph[node]

    for a in after:
        if a == n:
            print("POSSIBLE")
            sys.exit()
        q.append(a)
        dist[a] = dist[node] + 1

    curr = dist[a]

print("POSSIBLE" if dist[n] == 1 or dist[n] == 2 else "IMPOSSIBLE")
### BUGGY CODE ###

from pprint import pprint
import numpy as np
n,w=map(int, input().split())
wv=[list(map(int,input().split()))  for i in  range(n)]

dp=[[0]*(w+1) for i in range(n+1)]

for wsum in range(1,w+1):
  #print("重さ：{}".format(wsum))
  for i in range(n):
    #print("i={}".format(i))
    if wsum >= wv[i][0]:
        #print("選ぶ, (重さ：{}, 価値：{})".format(wl[i], vl[i]))
        dp[i+1][wsum] = max(dp[i+1][wsum], dp[i][wsum-wv[i][0]]+wv[i][1])
    else:
      dp[i+1][wsum] = dp[i][wsum]
    #pprint(dp)
dp=np.array(dp)
print(np.max(dp))


### FIXED CODE ###

from pprint import pprint
import numpy as np
import numba as nb
@nb.njit
def Knapsack1(n,w,wl,vl):
  dp = np.zeros(shape=(n + 1, w + 1), dtype=np.int64)
  for wsum in range(1,w+1):
  	#print("i={}".format(i))    
    for i in range(n):
      #print("重さ：{}".format(wsum))
      if wsum >= wl[i]:
        if dp[i][wsum] < dp[i][wsum-wl[i]]+vl[i]:
          #print("選ぶ, (重さ：{}, 価値：{})".format(wv[i][0], wv[i][1]))
          dp[i+1][wsum] = dp[i][wsum-wl[i]]+vl[i]
        else:
          dp[i+1][wsum] = dp[i][wsum]
          
      else:
        dp[i+1][wsum] = dp[i][wsum]
  #print(dp)
  print(dp[-1][-1])

n,w=map(int, input().split())
wv=[list(map(int,input().split()))  for i in  range(n)]
wv.sort(key=lambda x:(x[1],x[0]))
wv=np.array(wv)
wv=wv.T
wl=wv[0]
vl=wv[1]
#print(wl)
#print(vl)
Knapsack1(n,w,wl,vl)
### BUGGY CODE ###

n = int(input())

s = list(input())

ans = s.count("R")*s.count("G")*s.count("B")

for i in range(n):
    for d in range(1,n):
        j = i + d
        k = j + d
        if k < n :
            if s[i]!=s[j] and s[j]!=s[k] and s[i]!=s[k]:
                ans -= 1

print(ans)

### FIXED CODE ###

n = int(input())

s = list(input())

ans = s.count("R")*s.count("G")*s.count("B")

for i in range(n):
    for j in range(i+1,n):
        k = 2*j-i
        if k < n :
            if s[i]!=s[j] and s[j]!=s[k] and s[i]!=s[k]:
                ans -= 1

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

# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify
from collections import defaultdict
import copy
 
N,Q=map(int, sys.stdin.readline().split())
 
S=[]
event=[]
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	event.append(  ( s-x ,1, x) )	#Start
	event.append(  ( t-x,-1, x) )	#End


for i in range(Q):
	d=int(sys.stdin.readline().strip())
	event.append(  (d ,0, i) )

event.sort(key=lambda x:(x[0]) )

stop=set()

ans=defaultdict(lambda: -1)
is_stop=False
minstop=float("inf")


for s,flag,x in event:
	if flag==1:
		stop.add(x)
		if x<minstop:
			minstop=x
			is_stop=True
	elif flag==-1:
		try:
			stop.remove(x)
		except:
			pass
		if minstop==x:
			is_stop=False
	elif flag==0:
		if stop:
			if not is_stop:
				minstop=min(stop)
				is_stop=True
			ans[x]=minstop
		else:
			ans[x]=-1


for i in range(Q):
	print (ans[i])


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right

N,Q=map(int, sys.stdin.readline().split())

S=[]
event=[]	#x, s, t
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	heappush( event, (x, max(0,s-x) , max(0,t-1-x)) )


D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]
D.sort()
ans=[ float("inf") for _ in range(Q) ]

Next=[ i+1 for i in range(Q) ]	#Next


while event:
	x,s,t=heappop(event)
	start=bisect_left(D,s)
	end=bisect_right(D,t)

	i=start
	while i<end:
		ans[i]=min(ans[i],x)
		next=Next[i]
		Next[i]=end
		i=next

for x in ans:
	if x==float("inf"):
		print -1
	else:
		print x
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

for b, c in BC:
	A += [c] * b

A.sort()

print(sum(A[-N:]))


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

am = {}
for a in A:
	if not a in am:
		am[a] = 1
	else:
		am[a] += 1

for b, c in BC:
	if not c in am:
		am[c] = b
	else:
		am[c] += b

al = sorted(am)[::-1]

c, v = N, 0
for k in al:
	if am[k] < c:
		c -= am[k]
		v += am[k] * k
	else:
		v += c * k
		break

print(v)
### BUGGY CODE ###

def solve():
  n,m=map(int,input().split())
  res=[0]*n

  datas=[None]*m
  for i in range(m):
    x,y,z=map(int,input().split())
    datas[i]=[min(x-1,y-1),max(x-1,y-1)]

  datas=sorted(datas,key=lambda x:x[0])

  maxi=0
  for i in range(len(datas)):
    d=datas[i]
    if res[d[0]]==0 and res[d[1]]==0:
      maxi+=1
      res[d[0]]=maxi
      res[d[1]]=maxi
    elif res[d[0]]==0 and res[d[1]]!=0:
      res[d[0]]=res[d[1]]
    elif res[d[0]]!=0 and res[d[1]]==0:
      res[d[1]]=res[d[0]]
    elif res[d[0]]!=res[d[1]]:
      cor=min(res[d[0]],res[d[1]])
      dum=max(res[d[0]],res[d[1]])
      res[d[0]],res[d[1]]=cor,cor
      for i in range(len(res)):
        if res[i]==dum:
          res[i]=cor

  count0=res.count(0)
  ress=set(res)

  print(count0 + len(ress) - (1 if 0 in ress else 0))
  
solve()


### FIXED CODE ###

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

parent=[i for i in range(n)]
rank=[0 for i in range(n)]

def find(a):
  if parent[a]==a:
    return a
  else:
    return find(parent[a])

def union(a,b):
  ar=find(a)
  br=find(b)
  if ar==br:
    return
  if rank[a]>rank[b]:
    parent[br]=ar
  else:
    parent[ar]=br
    if rank[a]==rank[b]:
      rank[a]+=1
      
def same(a,b):
  ar=find(a)
  br=find(b)
  return ar==br

q=[None]*m

for i in range(m):
  x,y,z=map(int,input().split())
  q[i]=[x-1,y-1]

for i in range(len(q)):
  union(q[i][0],q[i][1])
  
roots=[0]*len(parent)
for i in range(len(parent)):
  roots[i]=find(i)

print(len(set(roots)))
### BUGGY CODE ###

n, m = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(m)]
ans = set(range(1, n + 1))

for l, r in LR:
  ans &= set(range(l, r + 1))
  
print(len(ans))

### FIXED CODE ###

N, M = map(int, input().split())
minNum = 1
maxNum = N
for lr in range(M):
  l, r = map(int, input().split())
  if minNum <= l and r <= maxNum:
    minNum = l
    maxNum = r
  elif minNum <= l <= maxNum and maxNum <= r:
    minNum = l
  elif l <= minNum and minNum <= r <= maxNum:
    maxNum = r
  elif r < minNum or maxNum < l:
    print("0")
    exit()
#  print(l,r,minNum,maxNum)
print(maxNum - minNum +1)
### BUGGY CODE ###

#!/usr/bin/env python3

import collections

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input()+'#') for _ in range(h)]+[['#']*(w+2)]
checked=[[False]*(w+1) for _ in range(h+1)]
checked[sy][sx]=True
q=collections.deque()
q.append((sy,sx))
ans=0
while 1:
  cur_pos=[]
  while len(q)!=0:
    y,x=q.popleft()
    cur_pos.append((y,x))
    for dy,dx in [[-1,0],[1,0],[0,-1],[0,1]]:
      if 1<=y+dy<=h and 1<=x+dx<=w and board[y+dy][x+dx]=='.' and checked[y+dy][x+dx]==False:
        checked[y+dy][x+dx]=True
        q.append((y+dy,x+dx))
  if checked[gy][gx]==True:
    print(ans)
    exit()
  if len(cur_pos)==0:
    print(-1)
    exit()
  ans+=1
  for y,x in cur_pos:
    for dy in range(-2,3):
      for dx in range(-2,3):
        if dy==0 and dx==0:
          continue
        if 1<=y+dy<=h and 1<=x+dx<=w and board[y+dy][x+dx]=='.' and checked[y+dy][x+dx]==False:
          checked[y+dy][x+dx]=True
          q.append((y+dy,x+dx))


### FIXED CODE ###

#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input().replace('\n','')+'#') for _ in range(h)]+[['#']*(w+2)]
scores=[[10**18]*(w+2) for _ in range(h+2)]
scores[sy][sx]=0
q=collections.deque()
q.append((sy,sx))
count=0
while len(q)!=0:
  y,x=q.popleft()
  for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]:
      scores[y+dy][x+dx]=scores[y][x]
      q.appendleft((y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dx==0 and dy==0:
        continue
      if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]+1:
        scores[y+dy][x+dx]=scores[y][x]+1
        q.append((y+dy,x+dx))
if scores[gy][gx]==10**18:
    print(-1)
else:
    print(scores[gy][gx])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
# A_dic = {A[i]: i for i in range(N)} #value: idx
A_items = [[A[i], i] for i in range(N)]
A_items = sorted(A_items, reverse=True)
# その時の最大のAに１つ使う　これを繰り返す
total = 0
rest = M
if N == 1:
    while rest > 0:
        rest -= 1
        A[0] //= 2
    total = A[0]
elif N == 2:
    while rest > 0:
        rest -= 1
        if A[0] >= A[1]:
            A[0] //= 2
        else:
            A[1] //= 2
    total = A[0] + A[1]
else:
    while rest > 0:
        temp_idx = A_items[0][1]
        while A_items[0][0] >= A_items[1][0]:
            rest -= 1
            A_items[0][0] //= 2
            A[temp_idx] //= 2
        idx = 2
        while A_items[0][0] < A_items[idx][0]:
            idx += 1
            if idx >= N-1:
                break
        u, v = A_items[0], A_items[idx-1]
        A_items[idx-1] = u
        A_items[0] = v
    total = sum(A)

print(total)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
A_dic = {} #value: idx
for i in range(N):
    if A[i] not in A_dic:
        A_dic[A[i]] = []
    A_dic[A[i]].append(i)

# その時の最大のAに１つ使う　これを繰り返す
total = 0
rest = M
if N == 1:
    while rest > 0:
        rest -= 1
        A[0] //= 2
    total = A[0]
elif N == 2:
    while rest > 0:
        rest -= 1
        if A[0] >= A[1]:
            A[0] //= 2
        else:
            A[1] //= 2
    total = A[0] + A[1]
else:
    hq = [-A[i] for i in range(N)]
    heapq.heapify(hq)
    while rest > 0:
    #     temp_idx = A_items[0][1]
    #     while A_items[0][0] >= A_items[1][0]:
    #         rest -= 1
    #         A_items[0][0] //= 2
    #         A[temp_idx] //= 2
    #     idx = 2
    #     while A_items[0][0] < A_items[idx][0]:
    #         idx += 1
    #         if idx >= N-1:
    #             break
    #     u, v = A_items[0], A_items[idx-1]
    #     A_items[idx-1] = u
    #     A_items[0] = v
    # total = sum(A)
        
        max_v = heapq.heappop(hq) * (-1)
        max_idx = A_dic[max_v].pop()
        A[max_idx] //= 2
        if max_v//2 not in A_dic:
            A_dic[max_v//2] = []
        A_dic[max_v//2].append(max_idx)
        heapq.heappush(hq, (max_v//2) * (-1))
        rest -= 1
    total = sum(A)
    


print(total)
### BUGGY CODE ###

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

for i in range(N):
    D*=A[i]
if  D>10**18:
    print(-1)
else:
    print(D)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
D=int(1)
ans=int(0)
A.sort()
if A[0]==0:
    ans==0
else:
    A.sort(reverse=True)
    for i in range(N):
        D*=A[i]
        if  D>10**18:
            ans=-1
            break

        else:
            ans=D
        

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

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

L=sorted(L, reverse=True)
count=0
for i in range(0, N-2):
    stop_count = 0
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            #print(i, j, k)
            if L[i] < L[j] + L[k]:
                count+=1
                stop_count=1
        if stop_count==0:
            break


print(count)

### FIXED CODE ###

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

L.sort()
#print(L)

ans=0
for i in range(0, N-2):
    for j in range(i+1, N-1):


        left, right = j, N

        while right-left > 1:
            mid=(left+right) // 2
            if L[i]+L[j] <= L[mid]:
                right=mid
            else:
                left=mid
        ans += left - j
        #print(i,j,left)
print(ans)
### BUGGY CODE ###

s = input()
t = input()
s1 = len(s)
count = 0
for i in range(s1):
    if(s[i] != t[i]):
        s.replace(s[i],t[i])
        count += 1
print(count)

### FIXED CODE ###

s = input()
t = input()

s1 = list(s)
t1 = list(t)

s2 = len(s1)
count = 0
for i in range(s2):
    if(s1[i] != t1[i]):
        s1[i] == t1[i]
        count += 1
        
print(count)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B = [0 for i in range(max(A)+1)]
C = [0 for i in range(max(A)+1)]

lenB = len(B)
for i in range(2, lenB):
  if i**2 > lenB:
    break
  if B[i] != 0:
    continue
  for j in range(i**2, lenB, i):
    B[j] = i
flag1 = False
flag2 = False
 
def func(X):
  global flag1, flag2
  while X>1:
    x = B[X]
    if x==0:
      x = X
    if C[x]==1:
      flag1 = True
    if C[x]==N-1:
      flag2 = True
    C[x] += 1
    while X%x==0:
      X = X//x
    #print(C)
for a in A:
  func(a)
#print(flag1, flag2)
if flag2:
  print("not coprime")
elif flag1:
  print("setwise coprime")
else:
  print("pairwise coprime")


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
 
B = [0 for i in range(max(A)+1)]
 
for i in range(2, len(B)):
  if B[i] != 0:
    continue
  for j in range(i, len(B), i):
    B[j] = i

def func(X):
  buf = set()
  while X>1:
    x = B[X]
    buf.add(x)
    while X%x==0:
      X = X//x
  #print(buf)
  return buf
 
set1 = func(A[0])
set2 = func(A[0])
totallen = len(set1)
for a in A[1:]:
  set3 = func(a)
  totallen += len(set3)
  #print(a, set1, set2)
  set1 |= set3
  set2 &= set3
  #print(set1, set2, set3)
#print(totallen, set1, set2)
if len(set2)!=0:
  print("not coprime")
elif len(set1)==totallen:
  print("pairwise coprime")
else:
  print("setwise coprime")
### BUGGY CODE ###

N = int(input())
s = []
ans = 0
for i in range(N):
        si = sorted(input())
        if si in s:
                ans += s.count(si)
        s.append(si)
print(ans)


### FIXED CODE ###

from operator import mul
from functools import reduce
import collections


def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    elif r < 0:
        return 0
    numer = reduce(mul, range(n, n - r, -1))
    denom = reduce(mul, range(1, r + 1))
    return numer // denom


N = int(input())
s = ["".join(sorted(input())) for _ in range(N)]
c = collections.Counter(s)
ans = 0
for si in set(s):
    n = c[si]
    ans += cmb(n, 2)
print(ans)
### BUGGY CODE ###

# e get everything
n, m = map(int, input().split())

lists = []
for i in range(m):
    price, num = map(int, input().split())
    K = list(map(int, input().split()))
    cnt = 0
    for some in K:
        cnt += 2**(n - some)
    lists.append((price, cnt))

dp = [[10**10 for i in range(2**n)]for j in range(m + 1)]
# dp[i][j]=i番目までの鍵を使用してjの状態を再現するために必要な最小の値
dp[0][0] = 0
for i in range(1, m + 1):
    price, mode = lists[i - 1][0], lists[i - 1][1]
    for j in range(2**n):
        dp[i][j] = min(dp[i - 1][j], dp[i - 1][j &(2**n-1-mode)] + price)

ans = dp[m][2**n - 1]

if ans < 10**10:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

# e get everything
n, m = map(int, input().split())

lists = []
for i in range(m):
    price, num = map(int, input().split())
    K = list(map(int, input().split()))
    cnt = 0
    for some in K:
        cnt += 2**(n - some)
    lists.append((price, cnt))

dp = [[10**10 for i in range(2**n)]for j in range(m + 1)]
# dp[i][j]=i番目までの鍵を使用してjの状態を再現するために必要な最小の値
dp[0][0] = 0
for i in range(1, m + 1):
    price, mode = lists[i - 1][0], lists[i - 1][1]
    for j in range(2**n):
        dp[i][j] = min(dp[i - 1][j], dp[i - 1][j &(2**n-1-mode)] + price)

ans = dp[m][2**n - 1]

if ans < 10**10:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

#!/usr/bin/env python

import sys

s0=[]
for i,c in enumerate(sys.stdin.readline().strip()):
    if c=="L": s0.append(i-1)
    if c=="R": s0.append(i+1)
n= len(s0)
#
table=[1,100,104,105,106,107,111,113,114,115,117,123,125,127,131,136,137,142,145,148,149,151,153,155,157,159,162,163,164,165,166,169,171,172,176,181,185,186,187,191,198,201,202,203,206,207,209,211,215,216,217,220,221,222,223,224,225,227,233,234,235,238,239,242,246,247,250,255,256,257,258,261,264,265,267,272,273,275,277,278,279,282,283,284,285,286,288,289,294,295,298,300,303,304,306,309,312,314,315,317,319,320,323,326,329,332]

now= [ i for i in range(n) ]
prev= s0
for i in range(1,333):
    nxt = [ prev[i] for i in prev ]
    if i in table: now= [ nxt[now[j]] for j in range(n) ]
    prev= nxt
#
ans= [0]*n
for i in range(n): ans[now[i]]+=1
for i in range(n): print( ans[i],end=" " )
    


### FIXED CODE ###

import sys

s0=[]
for i,c in enumerate(sys.stdin.readline().strip()):
    if c=="L": s0.append(i-1)
    if c=="R": s0.append(i+1)
n= len(s0)
#
now= [ i for i in range(n) ]
prev= s0
for i in range(17):
    now = [ prev[i] for i in prev ]
    prev= now
#
ans= [0]*n
for i in range(n): ans[now[i]]+=1
for i in range(n): print( ans[i],end=" " )
### BUGGY CODE ###

import statistics
import math
N=int(input())
X=list(map(int,input().split()))
for i in range(N):
  l=X[:i]+X[i+1:]
  med=statistics.median(l)
  print(med)

### FIXED CODE ###

N=int(input())
X=[int(x) for x in input().split()]
XX=sorted(X)
L=XX[N//2-1]
R=XX[N//2]
for x in X:
  print(L if x>=R else R)