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

N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
l=[[] for i in range(N)]
e=[0]*(N-1)
for i,(a,b) in enumerate(AB):
    l[a-1].append(i)
    l[b-1].append(i)
from collections import deque
q=deque([1])
e[0]=1
m=10**6
M=1
while q:
    pc=q.popleft()
    p,c=pc//m,pc%m
    for vn in AB[p]:
        x=1
        for en in l[vn-1]:
            if e[en]==0:
                if x==c:
                    x=c+1
                q.append(en*m+x)
                e[en]=x
                M=max(M,x)
                x+=1
print(M)
print(*e,sep='\n')

### FIXED CODE ###

N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
l=[[] for i in range(N)]
e=[0]*(N-1)
for i,(a,b) in enumerate(AB):
    l[a-1].append((b-1,i))
    l[b-1].append((a-1,i))
from collections import deque
q=deque([(AB[0][0]-1,1),(AB[0][1]-1,1)])
e[0]=1
M=1
while q:
    vp,c=q.popleft()
    x=1
    for vn,en in l[vp]:
        if e[en]==0:
            if x==c:
                x=c+1
            q.append((vn,x))
            e[en]=x
            M=max(M,x)
            x+=1
print(M)
print(*e,sep='\n')
### BUGGY CODE ###

import bisect
n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
ans=0
for i in range(n):
    j=bisect.bisect_right(b,a[i])
    for x in b[j:]:
        k=n-bisect.bisect_right(c,x)
        ans+=k
print(ans)

### FIXED CODE ###

import bisect
n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
ans=0
for i in range(n):
    x=bisect.bisect_left(a,b[i])
    y=bisect.bisect_right(c,b[i])
    ans+=x*(n-y)
print(ans)
### BUGGY CODE ###

N = int(input())
S = [sorted(list(input())) for _ in range(N)]
i = 0
A = []
for a in S:
    A.append("".join(a))

count = 0
for a in A[:N]:
    count += A[i+1:].count(a)
    i += 1

print(count)

### FIXED CODE ###

N = int(input())
S = [sorted(list(input())) for _ in range(N)]
import collections
A = []
for a in S:
    A.append("".join(a))
count = 0
c = collections.Counter(A)
for a in c.values():
    count += a*(a-1)//2

print(count)
### BUGGY CODE ###

import math
N = int(input())
for n in range(1, N+1):
  counter = 0
  if n < 6:
    print(0)
    continue
  x = 0
  x_max = math.ceil(1/3*(2 * math.sqrt(3*n-2)-1))
  while x <= x_max:
    y = 1
    x += 1
    while 4*n-3*x**2-2*x*y-3*y**2 >= 0:
      s = math.sqrt(4*n-3*x**2-2*x*y-3*y**2)
      if float(s).is_integer():
        s = int(s)
        if (s-x-y) >= 2 and (s-x-y) % 2 == 0:
          z = int((s-x-y)/2)
          #print("n:" + str(n) + "(" + str(x) + "," + str(y) + "," + str(z) + ")")
          counter += 1
      y += 1
  print(counter)

### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(10050)]
for i in range(1,105):
  for j in range(1,105):
    for k in range(1,105):
      v = i*i+j*j+k*k+i*j+j*k+k*i;
      if v<10050:
        ans[v]+=1
for i in range(n):
  print(ans[i+1])
### BUGGY CODE ###

import numpy as np
N, M = map(int,input().split())
As = list(map(int,input().split()))

As = sorted(As,reverse=True)
M_allocation = [0 for _ in range(N)]


argmax = 0
for i in range(M):
    As[argmax] = As[argmax]//2
    argmax =  np.argmax(As)
print(sum(As))






### FIXED CODE ###

import heapq

N, M = map(int,input().split())
As = list(map(int,input().split()))
As = [-1*e for e in As]
heapq.heapify(As)
for i in range(M):
    value = -heapq.heappop(As)
    heapq.heappush(As,-(value//2))
print(-sum(As))
### BUGGY CODE ###

h,w = map(int,input().split())
b = [[i == "#" for i in list(input())]+[True] for _ in range(h)]+[[True]*(w+1)]
#print(b)
check = []
for i in range(h):
  for j in range(w):
    if b[i][j]:
      check.append((i,j))
#print(b[-2][1])
ans = 0
while check:
  new = []
  k = 0
  for i,j in check:
    if not b[i-1][j]:
      new.append((i-1,j))
      b[i-1][j] = True
      k = 1
    if not b[i+1][j]:
      new.append((i+1,j))
      b[i+1][j] = True
      k = 1
    if not b[i][j-1]:
      new.append((i,j-1))
      b[i][j-1] = True
      k = 1
    if not b[i][j+1]:
      new.append((i,j+1))
      b[i][j+1] = True
      k = 1
  check = new
  if k:
    ans += 1
  #print(b)
print(ans)

### FIXED CODE ###

h,w = map(int,input().split())
b = [[i == "#" for i in list(input())]+[True] for _ in range(h)]+[[True]*(w+1)]
check = []
for i in range(h):
  for j in range(w):
    if b[i][j]:
      check.append((i,j))
ans = 0
while check:
  new = []
  k = 0
  for i,j in check:
    if not b[i-1][j]:
      new.append((i-1,j))
      b[i-1][j] = True
      k = 1
    if not b[i+1][j]:
      new.append((i+1,j))
      b[i+1][j] = True
      k = 1
    if not b[i][j-1]:
      new.append((i,j-1))
      b[i][j-1] = True
      k = 1
    if not b[i][j+1]:
      new.append((i,j+1))
      b[i][j+1] = True
      k = 1
  check = new
  if k:
    ans += 1
print(ans)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
#r1 = np.array(range(1,N+1))
#r2 = np.array(range(N,0,-1))
#X = (A-r1)
#Y = (A-r2)
#print(X)
#print(Y)
ans = 0
for i in range(N):
  X = A+A[i]
  r1 = np.array(range(-i,N-i))
  r2 = r1*(-1)
  ans += sum((X+r1)==0)
  ans += sum((X+r2)==0)
  #ans += (sum((X-X[i]*(1))==0)-1)
  #ans += (sum((Y-Y[i]*(1))==0)-1)
print(ans//2)


### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
r = np.array(range(N))
X = r+A
Y = r-A
ans = 0
x_dic = {}
y_dic = {}
for x in X:
    if x in x_dic:
        x_dic[x] += 1
    else:
        x_dic[x] = 1
  
for y in Y:
    if y in y_dic:
        y_dic[y] += 1
    else:
        y_dic[y] = 1

for x in x_dic:
    if x in y_dic:
        ans += x_dic[x]*y_dic[x]        
print(ans)
#print(X,x_dic,Y,y_dic)
### BUGGY CODE ###

a,b,c,d,e,f = map(int, input().split())
mx=0
swmx=0
smx=0

for i in range(0,31):
    for j in range(0,31):
        for k in range(0,101):
            for l in range(0,101):
                w=0
                s=0
                w+=100*a*i+100*b*j
                s+=c*k+d*l
                if w+s<=f and s<=e*w/100 and w!=0 and mx<100*s/(w+s):
                    mx=100*s/(w+s)
                    swmx=w+s
                    smx=s
print(swmx,smx)



### FIXED CODE ###

a,b,c,d,e,f = map(int, input().split())
mx=0
swmx=100*a
smx=0
 
for i in range(0,31):
    for j in range(0,31):
        for k in range(0,51):
            for l in range(0,51):
                w=0
                s=0
                w+=100*a*i+100*b*j
                s+=c*k+d*l
                if w+s<=f and s<=e*w/100 and w!=0 and mx<100*s/(w+s):
                    mx=100*s/(w+s)
                    swmx=w+s
                    smx=s
print(swmx,smx)
### BUGGY CODE ###

import sys
import collections
import itertools
import math
import re
from collections import Counter
from collections import deque
from collections import defaultdict

MOD = 10 ** 9 + 7

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

C = []

s = 0
ma = 0
for i in range(0,N-1):
    for j in range(i, N):
        if j==i:
            C.append(A[i])
        else:
            C.append(C[-1] + A[j])
    ma = max(ma, max(C))

IDX = 0
while ((1 << IDX) < ma):
    IDX += 1


def filterList(list, i):
    retList = []
    for l in list:
        if l & (1 << i):
            retList.append(l)
    return retList

D = C
for i in range(IDX,-1,-1):
    newD = filterList(D,i)
    if len(newD) < K:
        break
    else:
        D = newD


EE = list(itertools.combinations(D, K))
EE = list(set(EE))

ret = 0
for E in EE:
    r = E[0]
    for e in E:
        r = r & e
    ret = max(ret, r)


print(ret)

sys.exit(0)


### FIXED CODE ###

import sys

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

C = []

for i in range(0,N-1):
    for j in range(i, N):
        if j==i:
            C.append(A[i])
        else:
            C.append(C[-1] + A[j])

D = C
ans = 0
for i in range(40,-1,-1):
    yes = []
    no = []
    for l in D:
        if l & (1 << i):
            yes.append(l)
        else:
            no.append(l)

    if len(yes) >= K:
        ans += 1 << i
        D = yes

print(ans)

sys.exit(0)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = [0]*N

def bai_sum(A,n):
    global N
    sumup = 0
    for i in range(int(N/n)):
        sumup += A[n*(i+1)-1]
    return sumup % 2


for i in reversed(range(N)):
    if bai_sum(ans,(i+1)) != A[i]:
        ans[i] = 1
        
print(ans.count(1))

b=''
for i in range(N):
    if ans[i]==1 :
        hoge = i+1
        b = b+str(hoge)+' '

print(b)

### FIXED CODE ###

import math
N=int(input())
A = list(map(int,input().split()))
s = [0]*N
ans=0

for i in reversed(range(N)):
    floor = math.floor(N/(i+1))
    sum=0
    for k in range(1,floor+1):

        sum+=s[((i+1)*k)-1]
    if (sum - A[i])%2 == 1:
        s[i] = 1
        ans+=1

print(ans)
for i in range(N):
    if s[i] == 1:
        print(i+1)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
cnt=0
for i in range(n):
  for j in range(i+1,n):
    if a[i]==j+1 and a[j]==i+1:
      cnt+=1
      break
    else:
      cnt=cnt
print(cnt)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
cnt=0
for i in range(n):
    if a[a[i]-1]==i+1:
      cnt+=1
    else:
      cnt=cnt
print(cnt//2)
### BUGGY CODE ###

s=list(input())

num = s.count('W')

position = 0
for i in range(len(s)):

    if s[i] == 'B':
        position=i
        break

ans = 0

while num>0:

    for j in range(len(s)-1):

        if s[j]=='B' and s[j+1]=='W':

            s[position]='W'
            s[j+1]='B'

            position+=1
            dist = j+2-position
            ans+=dist
            num-=1

            break

print(ans)

### FIXED CODE ###

s=list(input())

num = s.count('W')

before = 0
for i in range(len(s)):

    if s[i]=='W':
        before += i


after = 0
for j in range(num):
    after+=j

print(before-after)
### BUGGY CODE ###

N, K = map(int, input().split())
p = [int(x) for x in input().split()]
ans = [sum(p[i : i + K]) for i in range(N-K+1)]

print((max(ans) + K) / 2)

### FIXED CODE ###

N, K = map(int, input().split())
p = [int(x) for x in input().split()]
s = sum(p[0 : K])
ans = sum(p[0 : K])
f = N-K+1
for i in range(1, f):
    s = s - p[i-1] + p[i + K - 1]
    if ans <= s:
        ans = s
print((ans + K) / 2)
### BUGGY CODE ###

n = int(input())
l0 = 2
l1 = 1
if n == 0:
    print(l0)
if n == 1:
    print(l1)

l_prev = l0
l_next = l1

i = 2
while True:
    l_new = l_prev + l_next
    if n == i:
        print(l_new)
        break
    l_prev = l_next
    l_next = l_new
    i += 1


### FIXED CODE ###

n = int(input())

l = [2, 1]
for i in range(2, n+1):
    l.append(l[i - 2] + l[i - 1])
print(l[n])
### BUGGY CODE ###

#coding: UTF-8

if __name__ == "__main__":
    N = int(input())

    fruits = []

    for i in range(N):
        fruits.append(input())

    count = 0
    fruitsCount = []
    fruitsCount.append(fruits[0])


    for f in fruits:
        if f in fruitsCount:
            count = count + 1
        else:
            fruitsCount.append(f)

    print(len(fruitsCount))

### FIXED CODE ###

#coding: UTF-8

if __name__ == "__main__":
    N = int(input())

    fruits = []

    for i in range(N):
        fruits.append(input())

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

N, Q = map(int, raw_input().split())
S = raw_input()
ac_counter = [0] * N
for i in range(N - 1):
  if S[i:i + 2] == 'AC':
    ac_counter[i] += 1
for _ in range(Q):
  l, r = map(int, raw_input().split())
  print sum(ac_counter[l - 1: r]) - ac_counter[r - 1]

### FIXED CODE ###

N, Q = map(int, raw_input().split())
S = raw_input()
ac_counter = [0] * (N + 1)
total = 0
for i in range(1, N):
  if S[i - 1:i + 1] == 'AC':
    ac_counter[i] += 1
  ac_counter[i] += total
  total = ac_counter[i]

for _ in range(Q):
  l, r = map(int, raw_input().split())
  print ac_counter[r] - ac_counter[l - 1] - (ac_counter[r] - ac_counter[r - 1])
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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 LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    h,w = LI()
    a = LIR(h)
    b = LIR(h)
    for i in range(h):
        for j in range(w):
            a[i][j] -= b[i][j]
            if a[i][j] < 0:
                a[i][j] *= -1
    M = 160*(5+((h+w)>>1))
    m = -M
    f = defaultdict(lambda : set({}))
    f[(0,0)].add(a[0][0])
    d = [(0,1),(1,0)]
    for y in range(h):
        for x in range(w):
            for t in f[(y,x)]:
                for dy,dx in d:
                    ny = y+dy
                    nx = x+dx
                    if 0 <= ny < h and 0 <= nx < w:
                        nt = t-a[ny][nx]
                        if m <= nt <= M:
                            f[(ny,nx)].add(nt)
                        nt = t+a[ny][nx]
                        if m <= nt <= M:
                            f[(ny,nx)].add(nt)
    ans = min([abs(i) for i in f[(h-1,w-1)]])
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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 LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    h,w = LI()
    a = LIR(h)
    b = LIR(h)
    for i in range(h):
        for j in range(w):
            a[i][j] -= b[i][j]
            if a[i][j] < 0:
                a[i][j] *= -1
    d = [(0,1),(1,0)]
    f = [0 for x in range(w)]
    M = (1<<25600)-1
    b = 12800
    f[0] = (1<<(b+a[0][0]))|(1<<(b-a[0][0]))
    for y in range(h):
        ny = y+1
        nf = [0 for x in range(w)]
        for x in range(w):
            nx = x+1
            if nx < w:
                f[nx] |= ((f[x]<<a[y][nx])|(f[x]>>a[y][nx]))
            if ny < h:
                nf[x] |= ((f[x]<<a[ny][x])|(f[x]>>a[ny][x]))
        if ny < h:
            f = [i for i in nf]
    ans = bin(f[w-1])[2:]
    ans = [abs(i-b) for i in range(len(ans)) if ans[len(ans)-i-1] == "1"]
    print(min(ans))
    return

#Solve
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

data  = [int(_) for _ in input().split()]
enemy = [int(_) for _ in input().split()]
#print(type(enemy))
#print(enemy)

if len(enemy) < data[1]:
    print(0)
    exit()

for _ in range(data[1]):
#    print(enemy)
    enemy.remove(max(enemy))
#print(enemy)

print(sum(enemy))

### FIXED CODE ###

data  = [int(_) for _ in input().split()]
enemy = [int(_) for _ in input().split()]

if len(enemy) < data[1]:
    print(0)
    exit()
elif data[1] == 0:
    print(sum(enemy))
else:
    enemy.sort()
    
    print(sum(enemy[:-data[1]]))
### BUGGY CODE ###

def MergeSort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    left = MergeSort(left)
    right = MergeSort(right)
    return MergeArray(left, right)

def MergeArray(left, right):
    merged = []
    li, ri = 0, 0
    while li < len(left) and ri < len(right):
        if left[li] > right[ri]:
            merged.append(left[li])
            li += 1
        else:
            merged.append(right[ri])
            ri += 1
    if li < len(left):
        merged.extend(left[li:])
    elif ri < len(right):
        merged.extend(right[ri:])
    return merged

def solve():
    X, Y, Z, K = [int(_) for _ in raw_input().split()]
    A = [int(_) for _ in raw_input().split()]
    B = [int(_) for _ in raw_input().split()]
    C = [int(_) for _ in raw_input().split()]
    A = MergeSort(A)[:K]
    B = MergeSort(B)[:K]
    C = MergeSort(C)[:K]
    lB = len(B)
    lC = len(C)
    sumAB = []
    for i in range(lB):
        tmpA = [ele + B[i] for ele in A]
        sumAB = MergeArray(sumAB, tmpA)
    sumABC = []
    for i in range(lC):
        tmpAB = [ele + C[i] for ele in sumAB]
        sumABC = MergeArray(sumABC, tmpAB)
    for i in range(K):
        print sumABC[i]

if __name__ == '__main__':
    solve()


### FIXED CODE ###

def MergeSort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    left = MergeSort(left)
    right = MergeSort(right)
    return MergeArray(left, right)

def MergeArray(left, right):
    merged = []
    li, ri = 0, 0
    while li < len(left) and ri < len(right):
        if left[li] > right[ri]:
            merged.append(left[li])
            li += 1
        else:
            merged.append(right[ri])
            ri += 1
    if li < len(left):
        merged.extend(left[li:])
    elif ri < len(right):
        merged.extend(right[ri:])
    return merged

def solve():
    X, Y, Z, K = [int(_) for _ in raw_input().split()]
    A = [int(_) for _ in raw_input().split()]
    B = [int(_) for _ in raw_input().split()]
    C = [int(_) for _ in raw_input().split()]
    A = MergeSort(A)[:K]
    B = MergeSort(B)[:K]
    C = MergeSort(C)[:K]
    lB = len(B)
    lC = len(C)
    sumAB = []
    for i in range(lB):
        tmpA = [ele + B[i] for ele in A]
        sumAB = MergeArray(sumAB, tmpA)[:K]
    sumABC = []
    for i in range(lC):
        tmpAB = [ele + C[i] for ele in sumAB]
        sumABC = MergeArray(sumABC, tmpAB)[:K]
    for i in range(K):
        print sumABC[i]

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

N = int(input())
S = input()
result = 0
'''
for i in range(N):
    print(result)
    for j in range(i+1,N):
        if S[i] != S[j]:
            for k in range(j ,N):
                if k- j == j - i:
                    continue
                if S[j] != S[k] and S[i] != S[k]:
                    result +=1
print(result)
'''

target = set('RGB')
for i in range(N):
    #print(result)
    for j in range(i + 1, N):
        if S[i] != S[j]:
            tmp = (target - set(S[i]+S[j])).pop()
            result += S.count(tmp, j + 1, N)
            if 2*j-i < N and S[2 * j - i] == tmp:
                result -= 1
print(result)

### FIXED CODE ###

N = int(input())
S = input()
result = 0
'''
for i in range(N):
    print(result)
    for j in range(i+1,N):
        if S[i] != S[j]:
            for k in range(j ,N):
                if k- j == j - i:
                    continue
                if S[j] != S[k] and S[i] != S[k]:
                    result +=1
print(result)
'''
r = S.count('R')
g = S.count('G')
b = S.count('B')
target = set('RGB')
result = r * g * b
for i in range(N):
    for j in range(1, min(i, (N - i - 1)) + 1):
        if target == set(S[i] + S[i-j] + S[j + i]):
            result -= 1
print(result)
### BUGGY CODE ###

N = int(input())
h = list(map(int, input().split()))
h.append(1000000001)
max_n = 0
for i in range(N-1):
    add = 0
    count = 0
    while h[i+add] >= h[i+add+1]:
        count += 1
        add += 1
    max_n = max(max_n, count)
print(max_n)

### FIXED CODE ###

N = int(input())
h = list(map(int, input().split()))
h.append(1000000001)
max_n = 0
counter = 0
while counter < N-1:
    add = 0
    count = 0
    while h[counter+add] >= h[counter+add+1]:
        count += 1
        add += 1
    counter += add +1
    max_n = max(max_n, count)
print(max_n)
### BUGGY CODE ###

def solve(string):
    n, *uvw = map(int, string.split())
    uvw = list(zip(uvw[::3], uvw[1::3], uvw[2::3]))
    whites = set([1])
    blacks = set([])
    while len(uvw) > 0:
        tmp = []
        for i in range(len(uvw)):
            t = uvw.pop()
            if t[0] in whites:
                if t[2] % 2 == 0:
                    whites.add(t[1])
                else:
                    blacks.add(t[1])
            elif t[1] in whites:
                if t[2] % 2 == 0:
                    whites.add(t[0])
                else:
                    blacks.add(t[0])
            elif t[0] in blacks:
                if t[2] % 2 == 0:
                    blacks.add(t[1])
                else:
                    whites.add(t[1])
            elif t[1] in blacks:
                if t[2] % 2 == 0:
                    blacks.add(t[0])
                else:
                    whites.add(t[0])
            else:
                tmp.append(t)
        uvw = tmp
    ans = ["0"] * n
    for i in range(n):
        if i + 1 in blacks:
            ans[i] = "1"

    return "\n".join(ans)


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(n - 1)])))


### FIXED CODE ###

N=int(input());p=[[]for _ in range(N+1)]
for _ in range(N-1):u,v,w=map(int,input().split());p[u].append((v,w));p[v].append((u,w))
s=[(1,0)];l=[-1]*N
while s:
 a,w=s.pop()
 l[a-1]=w%2
 for b,c in p[a]:
  if l[b-1]==-1:s.append((b,w+c))
for i in l:print(i)
### BUGGY CODE ###

n = int(input())
s_list = []

for i in range(n):
    s_list.append(input())
    
import collections
s_dict = collections.Counter(s_list)
max_s_dict = [k for k, v in s_dict.items() if v == max(s_dict.values())]
max_s_dict.sort()
for i in range (len(max_s_dict)):
    print(max_s_dict[i])


### FIXED CODE ###

n = int(input())
s_list = []
import collections

for i in range(n):
    s_list.append(input())

s_dict = collections.Counter(s_list)
maxv = max(s_dict.values())

keys = [k for k,v in s_dict.items() if v == maxv]
keys.sort()
for i in range (len(keys)):
    print(keys[i])
### BUGGY CODE ###

from collections import Counter, defaultdict
N = int(input())
A = [int(i) for i in input().split()]

f_list = [1]
for i in range(1, N+1):
    f_list.append(f_list[-1]*i)

def c(n):
    return f_list[n]//f_list[n-2]//2

m = Counter(A)
ans = defaultdict(int)
s = 0
for x, y in m.items():
    if y == 1:
        ans[x] = 0
    else:
        ans[x] = c(y)
        s += ans[x]
for a in A:
    print(s - (m[a] - 1))

### FIXED CODE ###

from collections import Counter
N = int(input())
A = [int(i) for i in input().split()]

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

m = Counter(A)
s = 0
for x, y in m.items():
    if y != 1:
        s += c(y)
for a in A:
    print(s - (m[a] - 1))